Do everything that everyone else here has stated, but also watch out for other things that they might fraudulently claim:

- Local listings - make sure that the Google local listing, and other local directories are showing the correct information, and that they didn't try to change this

- Social media accounts - What the scammy company would sell as "reputation management." Verify that they are not creating accounts on all of the big social media sites.