I have installed this fine-looking add-on (to a 2.2 site without previous SEO code) and, while I don't have it working quite yet, I have discovered two installation guide issues and a feature request. (I'm confident I can figure out the problems I'm having - if not, I'll ask here.)
1. The order of the eight edits is very nice, with each update in order so that the store isn't broken if you do them one at a time. Almost. Edits 7 and 8 should be in the other order - so that admin/includes/functions/general.php is updated to add the function before admin/categories.php is updated to use it.
2. A few pages back a user wrote that the add-on "suddenly started working", and you said that the user must have done something. Well, yes and no. The call to activate the contrib in application_top.php is made only if the "language" session variable is not registered. If the user had a browser session open and had been in the store recently, the language is established in the session so the SEO code is skipped until someone, who doesn't already have an active session, comes in. This might take a while in some stores. (It did for me, anyway.) The instructions should suggest closing all browser windows and then opening again to go to the site. This will clear the session cookie and establish a new session, triggering the activation.
Now the feature request - I would strongly suggest that the initial mode NOT be to have SEO URLs enabled, requiring the webmaster to turn them on. This would also give them the chance to look at the options and adjust if needed. In my case, I was getting 500 server errors (for reasons yet to be determined) until I turned the option off. I'd also like to see some sort of "test" mode that is enabled only for the store owner, again so they can try it out and perhaps make adjustments. I will hack this in myself so I can debug the problems I'm having, but I think it would be very friendly. I envision a session variable that can be set with a GET parameter or perhaps visiting a special page. You may have other thoughts.
The MSN links may or may not go away over time. See http://www.oscommerce.com/community/contributions,2819 for a contribution that will remove SIDs coming from search engine links. It is not foolproof, though.
One alternative I thought of, but have not tried, is to change the string that osC uses to identify the SID = "osCsid". If you change this to something else ("xyzsid" or whatever strikes your fancy), then all of the indexed links with SIDs will no longer have sessions. The risk is if you have customers currently in the store, they will lose their sessions as soon as this happens.