I'm posting this for the benefit of anyone, like me, who runs into problems using page caching with w3tc and an ad banner randomiser like AdRotate.
I tried all the solutions mooted on previous forum posts, like fragmented caching (wrapping the call to AdRotate in special tags to exclude it from caching) but none of it worked for me - the ads were always cached.
This, however, works, and is oh so simple.
Simply remove the call to AdRotate (e.g.
<?php echo adrotate_block(1) ?>) from your template file, place it into its own (new) file, and call it into the template via a php include instead. Then add this new file to the 'Never cache the following pages:' list in w3tc. Clear all caches and you should be good to go.