clients of certain isp cannot connect to my sites

Hi
I have a problem which I'm sure is common, it just has to be! Here's the specs of the problem, numbered so I don't forget anything:
1. I have a managed dedicated server ip 66.195.19.200 where I have all my sites hosted.
2. One particular isp prexar.com cannot resolve anything at that ip. Neither anyone that works there nor their clients connected to the isp can view my websites nor engage in any email in or out with my client's sites hosted on my server. i.e. if my clients are using their website as smtp and pop they cannot engage in email with any clients of prexar.com isp.
I think that's it. my nameservers are squeaky, I have rDNS, we're down to it being a router or network issue but the isp has informed me that it cannot be them, and I tend to believe it as they have checked everything. Does this sound familiar to anyone?? What are the possibilities os I have some "ammo" for either my web hsoting provider or the isp in question??

FYI...
I've had clients that when traveling to Europe, etc can't access certain websites to check email.
It is because the governments of various countries block access to certain IP ranges.

thank you

thank you. in this case, of course we're both on hte east coast of u.s. one in florida and the other in maine but it's definitely frustrating as both sides say it HAS to be the other and they have very convincing arguments both ways so I don't know which to trust, so I'm trusting neither! hehe.