The 301 'www' nightmare. How do I change back?

Disclaimer: I'm the author of http://www.yes-www.org/ and I'm glad you like it.

You've correctly identified a serious issue here, that of client-side and possibly even proxy caching of the 301 response. (Fortunately, search engines will pick up any change pretty quickly, so there's little to worry about there.)

On caching, RFC 2616 has this to say:

A response received with a status code of 200, 203, 206, 300, 301 or 410 MAY be stored by a cache and used in reply to a subsequent request, subject to the expiration mechanism, unless a cache-control directive prohibits caching.

Interestingly, browsers vary as to whether they actually cache 301 responses. Regardless of what you end up doing, you are almost certainly going to have some users who will need to clear out their browser cache.

With all that in mind, this is how I would approach the problem:

• At no time would I use a third subdomain, as my colleagues here have recommended. I don't see any reason it should be necessary, and a subset of your users are sure to notice and wonder if something is wrong.
• I would first change the existing 301 redirects from www to non-www to a 302 redirect. 302 is not cacheable by default. This I would leave in place for a period of time, perhaps 30 days, to allow search engines and the majority of your regular visitors to see it.
• At the end of that time, I would change the web site to use www, remove the 302 redirect, and place a 301 redirect from non-www to www.

While there will probably always be a user or two who will have to clear their cache to regain access to the site, regardless of what method you use, the number should be minimal, as users' caches aren't infinite, and even if they don't visit your site in the interim, they'll almost certainly visit many other sites which will likely push your old 301 out of cache due to its age and lack of use.

Your best bet is to have some sort of server-side logic, so when the request comes into example.com, check the referrer. If the referrer is www.example.com then don't do the redirect straight back to www.example.com, send them somewhere else, or just display the site for them, send them to a subfolder on www.example.com or whatever.

Also if you log these requests, you can get some good stats on how many users are coming from your www and still getting a redirect. Eventually that number should die down fairly low.

Also, remember to add your expiry headers to these 301's - then you won't have the issue that's described in the FireFox bug you linked to.