W3 Total Cache and Pronamics Cookies

The cookie set by Pronamic Cookies is pcl_viewed (see also https://github.com/pronamic/wp-pronamic-cookies/blob/develop/assets/pronamic-cookie-law.js#L26). Did this solve your issue?

Actually, for your plugin to be cache friendly, you’d simply just need to define DONOTCACHEPAGE in the blocker and show_message methods of your Pronamic_Cookies class, if the blocker is on or the message is being shown, eg:

if (!defined('DONOTCACHEPAGE')) {
    define('DONOTCACHEPAGE', true);
}

I’ve added the DONOTCAHEPAGE(see https://github.com/pronamic/wp-pronamic-cookies/commit/e946ccf4d79e9ee4e3fba6b834bd593516c77e09), this will probably be included in the next update of this plugin.

An other solution for this is use Memcached or XCache if you have (in the Page cache setting).
It works for me.