It may still be template/style related. If you use a completely unedited default XF style (you can create this if you don't still have it, just create a new style with no parent) do you still get the problem?
If it's still the same on the default XF style:
Do you have anything in your config.php file related to caching? This would generally be something you added yourself so you could try to remove it to see if it helps. Do you have any add-ons installed which have anything to do with caching? If not, then you will likely need to consult your host for more assistance.