had the same problem on my phone, wiped data cach and dalvik and after reinstalling Miui (last ver) i used the restore tool but only restored the apps everything else (system) i didnt restore and it seemed to do the trick , my market was updated to 3.5.16 and i am able to download and update everything.
I get the same. SGS2 miui 2.4.27...after a couple of reboots play store becomes market again and requires to reupdated. This results in excessive amounts of unnecessary 3g data. Can you please keep in mind for next release?
so this is what i did and it works
1)download Google Play.apk ver 3.5.16(latest) and rename it to Phonesky.apk
2)delete vending from /system/app
3)now copy the google play store which u renames to phonesky.apk to /sysyem/app over right it
4) restart phone