Why would they provide your mailing address in the Whois? Are they that black-hat bent? I don't even know what purpose that would serve, as no average customer of yours or theirs would ever be bothered with the information in a Whois record. Haha, I guess they think that maybe the registrar will send the domain bill to you guys? That would be classic.
I don't know what the penalty is for providing false Whois info, but I would take it that the only leg you have to stand on, if any, is ironically the fact that they're putting you down in the Whois. I would go that route, contacting the registrar perhaps, and your lawyer. But as far as the name itself, the domain is theirs; you have no rights to it, as is my understanding. If it is important enough to be worried about now, it was probably important for you to purchase it back when it was available.
After all, your competitor has registered the domain in your name, so it's really yours... ;)
Good luck