Actually I have some good news.
It would seem that MR4 did actually do something. I have been testing on my own Handheld to verify whether the policy had taken effect, with only the "Error" message, since the MR4 update.
I decided to test one of the users Handhelds, who was previously wiped and re-activated with my "New Policy", and it changes policy without error. (This wasn't the case pre-MR4)
So I'm going to wipe and re-activate the 3 offending Handhelds. With the majority of the Userbase able to receive updated/new Policies i'm happy with the BES's functionality now.
I'll probably leave my own Handheld in an error'd state just to see if i can fix this error. If i do figure it out i'll be sure to post about it here.
Special thanks to the Gibson_SG
Looks like i do owe you a beer.
Cheers