Actually, according to the CRM 2011 SDK documentation the sitemap modification thas was part of the managed solution should automatically be removed from the system when the managed solution is removed. Quoted from the SDK doc:
When a solution is packaged as managed, the SiteMap XML is compared
to the original SiteMap XML and any other customizations made to the
SiteMap. Only the differences are included in the managed solution.
These differences include items that are changed, moved, added or
removed .... Later, if the managed solution is uninstalled, the
SiteMap XML that was imported with the managed solution will be
referenced to remove the changes introduced with that managed
solution. A new active SiteMap is then calculated.
For example, the customization.xml of a solution containing just an added Group will contain XML similar to this:
<Group Id="TestGroup" IsProfile="0" ordinalvalue="6" solutionaction="Added">
<Titles>
<Title Title="Examplegroup" LCID="1033" />
</Titles>
<SubArea Id="new_webresource" PassParams="1" Url="$webresource:new_webresource" ordinalvalue="0">
<Titles>
<Title LCID="1033" Title="Example" />
</Titles>
</SubArea>
</Group>
The solutionaction attribute instructs the system to remove the snippet of XML from the full customization.xml when the managed solution is removed. In short, it should behave the way that you want it to...
Of course, the above only applies to managed solutions.
That is doesn't work for you seems to indicate that the customization.xml of your system has somehow been corrupted. I would recommend exporting the sitemap, remove any reference to the erroneous elements, and re-import.
It should also be noted that you usually need to do a hard refresh of the web browser after publishing an update to the sitemap, in order for the removed navigation elements to go away. Otherwise it's easy to run into problems similar to the ones that you describe.
