What about caching? I have had problems in the past that sound like exactly like yours. The reason for the admin section always working is that these are usually not cached. Do you have a cache plugin enabled on your site or does your htaccess enable caching?
