Well it's fixed. The host installed a new nic on the box and assigned it a public address. Now I had people here use the ip address of the new nic as a temporary fix. I come in this morning and the host name resolves and I think Hummm.... So I check out my local DNS server and the new ip address is listed. Strange, so I check out www.dnsstuff.com and sure as s**t, there's the new address.

Don't know if their isp was filtering or if their DMZ had a glitch, either way they changed their public address over the weekend.

They finally figured out it wasn't an issue on my end. And I'm done second guessing myself.

Thanks all for the replies.