Sometimes if you're performing several stsadm commands (like adding, deploying, upgrading, and/or removing solutions) SharePoint get's some things stuck and it then proves to be a bear to get it out.

For example, we upgraded a solution for a customer using stsadm and we were receiving an error stating we couldn't upgrade the solution. So we removed the solution completely and then tried adding it. We then received an error stating that the feature with this ID already exists. So we went ahead and removed it again and deleted the associated folders from the features folder. Tried to readd it and received the same error. We then changed the id of the feature and then received the error that the folder was already in use by another feature id. Yeah, real fun.

One of the error we received was

The solution can not be deployed.  Directory "FeatureName" associated with feature '90d332d5-e3bc-4eb3-8e7e-4832a6809f5e' in the solution is used by feature 'f59233ef-a1e6-4bf8-b635-8c024a7397b2' installed in the farm. All features must have unique directories to avoid overwriting files.

So even though the feature was not installed, it was acting like it was. I'm guessing it was stuck in the config database. We ran stsadm -o uninstallfeature to remove the feature and that worked! What a bear.

Hope this helps!