I think something odd is going on... I haven't heard of other folks having this issue, and I'd think I would have if its happening so often.
Are you using the latest image (0.5c)? You might want to grab a fresh copy even if so.
Are you applying the fixes? Try applying all, then rebooting (just ignore the Xauth error if you see one). Does the problem go away?
Edit--- some other thoughts enter my head...
How quickly after power up are you doing this? The setup scripts have some delays to let X get loaded, and only at the end do they arrange the xauth stuff and make ssh work properly. Slow USB keys can make this time even longer. If you are jumping in before these run, you'll get bad results.
Second... why not just get it to work once, and then copy that key back to whatever PC you are using to write the stock image. Now make all future images from that new image.
Third.. how often are you reinstalling that this is actually an issue?
I did not know we can copy the key to other systems, that's a good idea.
It might have something to do with SSHing in before the system is ready for me, I have a tendancy to jump in right away.
Right now everything is running 100% using BAMT with the exception of the 7970s being not compatible (my boss is going to give the 30BTC pledge for compatibility shortly).