A: 

I suspect the problem could be during the authentication between client and server, because every other stream.publish call works except for the first.

Try setting 'cookie' to false in FB.init... I reasoned that might force the init to actually contact the server

FB.init({

...

cookie:  false,

...

});

Haven't thoroughly tested it, but it seems it might just work.

UPDATE: unfortunately, it seems it won't fix it for all the cases

Ivko Maksimovic
there is yet another tread about this issue:http://forum.developers.facebook.net/viewtopic.php?pid=239419
Ivko Maksimovic