After looking through it I found a fix, our security guy asked us to turn the 'useOAEP' flag to 'true', I removed this and the encryption and decryption works perfectly!
I wish I could explain why this fixed it but when all your provided is a dumb error message (Bad Data!) you can't exactly expect a smart explanation.
Here's what our encryption headers looks like now:
<configProtectedData defaultProvider="ApplicationProvider">
<providers>
<add name="ApplicationProvider"
type="System.Configuration.RsaProtectedConfigurationProvider, System.Configuration, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL"
keyContainerName="ApplicationProductionKeys"
useMachineContainer="true"/>
</providers>
Hopefully this will save others a few inches on their hairline when they attempt encryption