So I seem to have found the culprit. As stated in the master page we are removing the values for
<input type="hidden" name="__EVENTTARGET" value="" />
<input type="hidden" name="__EVENTARGUMENT" value="" />
This seems to cause an issue with certain javascript postback events. I found a really good article here saying what they do.
http://aspalliance.com/895_Understanding_the_JavaScript___doPostBack_Function.all
These two hidden fields control any linkbuttons that do a JavaScript___doPostBack call but do not affect normal buttons or image buttons as they do a proper postback to the server.
Checking the post I can see that when clicking the paging link the values are:
__EVENTARGUMENT - Page$2
__EVENTTARGET - ctl00$MasterContent$gvBenefitsList
Even though viewstate is switched off these fields are still used for these events.
Hope this helps somebody out. I've been struggling with it for a while!