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