When it comes to webhosting, you can't beat NearlyFreeSpeech. They're cheap, fast, and reliable. I've been a very happy customer for years, and run a number of Drupal installations under them.
However, NFSN does do things a little differently, and this can cause some interesting interactions with Drupal. The main thing that they do differently is that they use Squid and run reverse proxies at the edge of their network, which cache requests made to member websites. For most sites, this is not a problem. Drupal, however, tries to be "cache friendly" with regards to the headers it emits, and sometimes this doesn't work so well. I've seen the following symptoms happen under a virgin Drupal installation:
Here's how to fix that:
By examining that line, you can tell whether you are retrieving the most recent copy of the page or not, and this can be a valuable tool in troubleshooting cached pages.
Once all of those things are done, any cache issues that your users are experiencing should slowly go away.
Finally, I must admit that I am not any sort of HTTP guru. I merely followed what I read in these specifications:
http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.9.2
http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.9.4
If you know of a better way to fix this problem, feel free to let me know...