Themes and Caching issues

I just recently launched a Drupal website with a custom theme and I'm having troubles with caching (I think).

http://www.oakandmistletoe.com.au/

First of all, I realize the theme has IE6 issues -- I'm working on that. What are you doing using IE6 anyway!? Get a real browser!

It's a 6.13 site. The theme itself is based off of the excellent Framework theme. The site is hosted on a Dreamhost shared account. The audience is global -- mostly US, Australia and Europe.

The biggest problem is that, fairly often certain people will visit the site and it appears totally without the theme -- plain HTML, no CSS, no graphics. This seems to coincide with my flushing the theme cache via Devel. As in, it will start happening for certain people shortly after I do this. When this does occur, I ask them to do the ol' shift-refresh, but that doesn't seem to have any effect.

The second problem is that old graphics which have been replaced are appearing for certain people fairly often. For this issue, shift-refresh does work, however it's just not practical to tell every user to shift-refresh to get the latest version of the site every time they visit.

I'm wondering first of all why the missing theme issue could be happening, and secondly, what I need to change to optimize the cache settings. Already I have the site settings under Performance set to not cache anything. (This is probably not the right way to go, either.) I've wondered if this is an .htaccess issue. I'm using the default .htaccess file that ships with Drupal.

I've done a lot of searching here and elsewhere. A large part of the problem is that I'm just not sure what exactly the problem is -- whether it's the host, the way the theme was constructed, .htaccess or some admin settings. Any insight anyone can lend to this issue would be incredibly appreciated. Even if it's just a link to something that I can read up on.

Thanks!
Julia