Since the URL is the same for new visitors and returning visitors, any kind of page caching (w3tc or another like super cache) would mix up the messages, showing the message of whatever user primed the cache.
The best alternative I can think of would be to use javascript (even an ajax call to a custom page that displays the WWSGD message) to display the message. As far as I know you’d need to create your own code to do this.