I blocked a page in robots.txt under User-agent: *, and tried to do a manual removal of that URL from Google's cache in the webmasters tools. Google said it wasn't being blocked in my robots.txt, so I then blocked it specifically under User-agent: GoogleBot and tried removing it again and this time it worked. Does that mean Google doesn't respect User-agent: * or what?
GoogleBot should properly follow rules for
User-agent: *, however it will not update it's cache until it GoogleBot has crawled your site again, which takes some time. Google doesn't release the exact minimum time between crawls, but I'd speculate it's about 15 to 30 minutes.
Incoming links will also make the url indexed by google. It wouldn't have an index of the actual content
If webmaster tools said it wasn't being blocked by robots.txt, I'd say you must have had an error in your robots.txt file. Google definitely does honor User-Agent so something else must be wrong. You can check out robots.txt in some detail via the help pages under Google Webmaster Tools.
Index removal takes 24-48 hours in my experience, although I have seen it happen in as little as 5 hours.