I can now confirm that all CDO components are in check and correct. I can also now say with absolute certainty that when the BB redirection is turned off the issue will not appear... as soon as it is enabled again the problem comes back. I feel like I am assembling a band with the amount of people I now have on the case. MS/RIM/O2/You friendly folks.
For reference I have also updated our BES server which is 4.1.4 to the latest MR's, unfortunately the issue did not go away although a brand spanking new one appeared which is some C++ error when doing an "update check status" on the BES... the joy.
I will keep digging and update as soon as I get some tangible info from MS.. they have a large number of client logs to work through now too.