ServiceScrubber edits the Info.plist of the applications, and though I don't know the details, it seems to me that this is how it pulls off its feat. I believe that is why the customizations are usually undone when you upgrade an application such as OmniOutliner. I find I have to make the changes using ServiceScrubber again and again, seemingly whenever I update an application, presumably for this reason.
A solution would be a mechanism that watches the plist files that you've customized for changes (as is very easily implemented using launchd), and confirms whenever they are overwritten that you want to restore your customizations to the service menu. Perhaps implement this or suggest it to the developer of ServiceScrubber (while making a donation...)