Well, they are obviously scammers and the complaint is clearly bogus (it's doesn't even make sense). They create the "problem" and offer to fix it (for a free of course).
Login to your Google Webmaster tools and report them. I'm sure Google has seen this kind of stuff before. If they will remove it or now, I have no idea (probably not = too much time to investigate).
How many people actually come to the website for the search term you listed? Does it matter? If it's significant and THAT important - ask your client to hire a lawyer.
The dirty: You could easily knock them off the main page of Google with a couple of freebie blogs targeting the keywords. Unfortunately, you might knock yourself off too.
Sorry, I couldn't be of more help.
Good luck!
Risto
Bookmarks