Isn't it pretty risky to have a business rely so heavily on a 3rd party (Google) with whom you, presumably, do not have a business relationship? If your business is vulnerable to being hurt simply due to some other company "doing SEO", maybe consider trying to address that weakness directly rather than just riding it out or trying to SEO back at them. I don't think I'd have the guts to start a company that depended so heavily on the whims of Google's search algorithm.