I have an internal DNS Server. It's running on Windows 2003 Server, although this problem was happening when it was on 2000 Server as well.
There are a bunch of hosts (A) in there, and several aliases (CNAME) as well. The A records seem to always work, however; the aliases will stop responding on a fairly regular basis. Maybe 3 times a week, a query for any alias will start failing. This happens to a handful of users, although I suspect that others just don't mention it. It doesn't happen to everyone at the same time, so it's not strictly a server problem. I know it has to do with client/server interaction.
I've found that issueing "ipconfig /registerdns" fixes the problem immediately. I'm running Win2K Pro SP4.
I suspected negative caching, but I don't need to flush the cache to fix it, just the registerdns (maybe this flushes the cache as well....). I know I can turn off negative caching, but I can't remember how (that's not what the points are for!).