I have a new client on my server, since the account has been created the client reports random downtime. Trace route reports host not found. I have triple checked all DNS settings, they are fine.

Every time I try to look at the site its fine, I asked someone in another state to try and view it and it was down for them but up for me. Tonight I asked someone 3 miles away to try and it was down for them and again up for me at a different location..

I really have no idea why this is happening. All name servers are correct, DNS is correct.