It's been a while since I've looked into these "reputation" services. Do they actually work, when not hit by the Streisand effect, or is it just snake oil?
At first I couldn't figure out what was going on. Why would someone be writing "Great post!" on 20 of my stories at 11:30 p.m.? Then I did a little checking on the names of the posters. Turns out they all had some "incident" in their pasts. Now they or their consultants were pumping out huge amounts of bland, benign content from all sorts of accounts (news sites, Tumblr, etc.) in their real names. The net result: these new accounts and the resulting content swamped Google, becoming the top 50 or so search results. The bad stuff didn't totally vanish, but it now was relegated to much lower placement.
In terms of whether this stuff works, that's a tricky call. I think it all depends on what the nature of the client's problems are ... and how much the world can/should care about some past mistake as life plays out. Sometimes it's hard to argue with the desire for a fresh start. In other case, it's hopeless.
Of course you didn't, because that would be mean, yet oddly satisfying.
I always thought these were linkspam bots, hoping to get a little pagerank from the url they submit with their name
As far as I know, punishment for the perjury has never happened. The only case I know of where legal fees were paid is Automattic vs Steiner.
There are at least four rich convicted felons who have Wikipedia articles and paid editors trying to whitewash them. They haven't succeeded.
Years later, that obscure person gets caught up in an Internet-(infamous) scandal...and instead of just a bunch of self-made pages via LinkedIn, About.me, etc., that they can delete, they now have a suspiciously-seeming astroturfed Wikipedia entry with a prominent "Scandals/Controversy" subhead. And Wikipedia's pagerank being what it is...virtually no reputation-astroturf effort will overtake it.