What should happen is removing the addon should empty the caches, so that things like a cached admin menu block will no longer try and link to modules that no longer exist.

A couple of possible things have been known to break this:

1) A page request happens while the addon is being removed, and happens to regenerate something decached by the addon removal with stale data from before the addon removal is completed. Decache happens at the end of addon removal, but if something else decaches it first, the other request can re-cache it and save it after the addon does its own decaching. i.e. It overlaps in a bad way.
This issue can be easily worked around by manually clearing caches.

2) If somehow an addon removal is not complete (or something manually interferes with what files are on disk), Composr can be in an inconsistent state. This mainly happens if addon hooks exist without all the files (or database tables) relating to the addon.

I can't reproduce the issue right now, so I'm assuming it's one of the above.