www. domain problem on dedicated

[nomi]

I have had this weird problem where domains at any time in the day or night stop responding to www.domain.com and only work with http://domain.com this fixes itself later. This is really weird. Not just me, 4 of my clients from different parts of the world are having similar problems. I cannot understand what could possibly be going on. Anyone have any suggestions? Any ever have this problem and knows the solutions?
www.domain not working but http://domain working. Please note that i have checked the DNS Zone, which is attached.

[sonixi]

I used to have this problem on Cobalt RaQ servers. I think it has something to do with your name servers not updating each other properly.

[nomi]

Thats what my dedicated server provider said and im trying to fix it right now :D, thanks for the conformation.