I just tried to reproduce what you have done, and it looks like that you
have to put in the directory, from which you start the application
(working dir, "."), the fbembed.dll, icudt30.dll, icuin30.dll and
icuuc30.dll (rest can remain in %FIREBIRD% dir, at least that is my
impression).

My test batch file looks like this (Windows 7, 64 bit):

@echo off
set JAVA_HOME="C:\Program Files (x86)\Java\jdk1.6.0-32bit"
set FIREBIRD="D:\Program Files\Firebird.2.1.3-embed"
set PATH=%PATH%;%JAVA_HOME%\bin;%FIREBIRD%

echo %PATH%

%JAVA_HOME%\bin\java -Djava.library.path=%FIREBIRD% -classpath
.;jaybird-full-2.1.6.jar %*

This combination works.

Trying to set the %FIREBIRD% does not work, though it should. Without
copying icu*.dll files it won't work either. At least on Windows 7
(maybe there were some API changes regarding the library loading). I did
not start it in debugger to see where it crashes, but I will do this soon.

Roman