Having inherited the servers in the state that they were configured, I never questioned the validity of the keys!!! ...Just checked that they matched on both servers...
Leaving all the encryption / decryption and validation algorithm settings as they were, I generated new keys using this tool which has a few more options than the others.
Problem solved
Moral of the story: If in doubt, generate new keys
... but why and how? Some postbacks with viewstate were working just fine with the old keys, it was only when the postback was to a different server that the problem became evident. If the keys were invalid - missing a character or something - then every postback should have failed - I think