Unfortunately I couldn't reproduce this issue on default 5.0 and 5.5 installation.
In both cases:
1. I created Image gallery page
2. Inserted Media Galery webpart to this page
3. Changed Properties of Media Galery webpart (set Media library: Czech nature - this media library is in default Corporate site).
4. I removed the first image in Czech nature media library in CMS Desk - Tools - Media librariies - Czech nature
5. The image was removed in CMS
Desk - Tools - Media libraries - Czech nature library
6. The image was removed in CMS Desk - Content - my image media library page (only second image was displayed).
Could you grant us with an access to your system to check behavior you described? You can send it to firstname.lastname@example.org.
Could you also tell us what your Cache setting is?
A) In properties of your media library page - General - Cache (CMS Desk)
B) In Site Manager - Settings - Web site
So far it seems to be same caching issue.