I had this twice and was fortunate enough to use SEUS on both occasions.
Even with the wrong firmware using a2uploader SEUS still picked it up.

What OS are you using?
I could not get Vista or Windows 7 to recognise the phone on all occasions, flash properly or work on all usb ports but on XP it went fine.
Doesn't sound like we have the same problem though, you are using two firmware types aren't you and taking the battery out at the correct times.
Just making sure you are doing it all right though it sounds like you are.