Whilst I don't know why this was happening, I changed the code to use AES encryption instead - this is working fine.
While not an answer to the problem per-say I think it's a valid workaround that deserves mentioning.
EDIT:
I think I've found what was causing the issue (I still don't exactly know WHY this is happening, but I did notice something today).
If the web application is using the ApplicationPool identity, then all is fine and well and DPAPI should continue working after an IISRESET. However if I change the identity to a specific user defined in AD, then things go haywire after the application pool is recycled.
Lucky for me In this particular case I neither need a specific AD user any more and the main encryption is based on AES (DPAPI can't be used to access a shared resource when load balancing comes into the equation) with DPAPI only being used to encrypt the local copy of the AES keys.