Man-in-the-middle'd by my marketing firm?

Okay, so a little backstory: I started having some intermittent issues contacting my domain controller. Lots of machines losing their connectivity, logins failing, dropped connections to the file share, etc. One machine went down completely. I set to troubleshooting. We'll call my domain contoso, for the sake of readability, and I'm sure you've all heard the reference.

So, start running tracerts and pings, and just establishing a baseline for my network, which is admittedly janky as a fox, but that's a different (albeit, embarrassing) post.

Everything seems to be resolving, IPs are coming back with replies, etc. Then someone suggests I try nslookup on Amazon, just for kicks. I get a reply, but it isn't what I expected.

"amazon.com.contoso.com" and an IP that is most definitely not Amazon. I check into it with Firefox, and look into the cert, and it comes back to my media company - let's call them Citycenter.

What happened, here? Did they likely do a web crawl, and find my name and address as the domain registrant, realize it belonged to us, and stick it under their umbrella? Could that be causing my issues? I have machines on my net that return DC.contoso.com as the same funky address as the Amazon lookup. Is that my connectivity issue? I just don't know. The issue is super intermittent, and sometimes the machines work fine, other times I lose my domain trust relationship, but it's hard to see, since my users sit at their desks and run on cached profiles.

For reference, my net is basically all my machines, DC included, tied into a dumb switch, which is tied into my router. Incidentally, wireless connections to the router are not capable of connecting to the domain, guest network or otherwise - but I suspect that's a misconfig on my part I'll address in another post.

Is this my media company's problem? We have our outward web domain, which they manage, so I don't know why they pulled this under their umbrella. But it's an annoyance, and they're telling me that they may not be able to fix it right away, all things considered. What can I do?