Re: Never use the REMOVE TOOL...

10 out of 10 for you, Bah bahed!

Sorry, I'm very sarcastic today, I should lay off of espresso in the
evening. (serious face on)

File a reinclusion request, they can get it back in even if you files
to get it removed.
http://www.mattcutts.com/blog/reinclusion-request-howto/ . Tell them
EXACTLY what you did (and why you thought it would work -- Google can
learn from these things as well). Usually they're very good at getting
it back, if it is a problem from the removal tool or something similar.
At the same time, it might be a good idea to really clean up everything
on the site because you can be sure they'll manually review your site
before returning it into the crawler queue :-)

And yes, Google does seem to sometimes throw up old, cached data for
seemingly no reason at all... sometimes we just have to deal with it
and at least make sure that any traffic coming in that way will get
routed to the desired locations. It's a bit of work, but doable.

Good luck!
John