Symptoms
When navigating to the sitemap2.aspx or googleindex.aspx the page is redirected to InvalidRequest.aspx and an error occurs with the message line "The given key was not present in the dictionary"
NOTE: This pertains to ML/MultiStore versions 9.0.1.3SP1+Admin and earlier.
Cause
The most common cause is when an entity (Category, Department, Manufacturer, etc.) has been UNPUBLISHED while containing PUBLISHED sub-entities.
Solution
In the admin console of the storefront, go to the Organization menu and manage each entity, looking for any UNPUBLISHED entities (showing the 'Publish' link) that contain sub-entities (parent entities with a plus sign to the left). You will want to check the box above the grid to 'Show Deleted', and expand the sub-entities with the plus sign to the left of the unpublished parent entity, and then UNPUBLISH (click the 'Unpublish' link) any published sub-entities. Be sure to go through all sub-entity levels. Reset Cache and check the sitemaps again.