We have noticed that when after retracting a MOSS solution package, we are still left with incorrect leaf entries in the alldocs MOSS database table. This is an issue if for example we rename a feature that deploys the same artifacts - MOSS will then not let us deploy the solution as it thinks these items already exist.
Would be interested to hear if anyone else has had this problem.
Depending on the solution, SharePoint doesn't always clean everything up. However you must never touch the SharePoint database! Even querying it is not supported as this can cause locking issues that will make the application unreliable. Also see KB 841057.
There should always be a way to solve the problem via the SharePoint API. Once you've found it, add the clean up code to a feature receiver so that it executes when the feature is deactivated. If you need help, please ask in a new question with the code/schema you are using.
Depending on the error you are receiving, the tools on these pages may also help:
I Agree with Alex, this shouldn't concern you and the fact that you've noticed this means that you have more than a a healthy interest in the sharepoint DB.
Practical explanations maybe that you created assets (e.g. listitems) that have references to the solution (content types, site columns etc) and so these are orphaned when the solution is removed, of course when you re install the solution these assets will work correctly so its not all bad.