I ended finding a couple of solutions to this problem.
It seems that the root of the problem is that page cache is no longer using the parameters passed to the page for its caching key, its therefore treating the content of the ajax loaded page the same as the initial load and caching over top of it. I traced this back to a new function
Enterprise_PageCache_Model_Processor_Category::_filterInputParameters where the get parameter I was using, in this case
p for page, was being stripped out. It seems that there is a whitelist of parameters held in
$_paramsMap which are allowed, every other parameter is stripped out.
I resolved this by overriding Enterprise_PageCache_Model_Processor_Category and creating a new
$_paramsMap property which contains my custom
p parameter. This seems to have resolved my issue.
UPDATE - SUPEE-9465
After digging further I found this post which basically summed my issue up to a tee. It seems that there is an official Magento patch which basically just removes the
_filterInputParameters function altogether. I haven't actually seen the SUPEE-9465 patch through offical Magento channels but the linked gist seems to be a legit solution.