Have you tried deleting the profiles from MIAB
Read here iPad Profile won't log in - #3 by stylnchris
z-push-admin -a remove -d Device ID
Also delete and add all MS Active Sync accounts on your devices.
It seems you are right that after each update push messages stop. I just noticed on my Iphone.