Okay, so what I think is happening is that the Media Replace plugin is not quite as smart as it should be. We have a number of images that are named with the structure... house.png, house-door.png and house-door-window.png. When wordpress creates it's different sizes it saves those out with dashes, so those three images would be house-103x100.png, house-door-103x100.png, and house-door-window-103x100.png.
I think the plugin says, okay... you want to replace house.png so I'm going to delete house.png and all it's sizes (house-X.png). In doing so, it deletes house-door.png (and it's sizes) and house-door-window.png (and it's sizes).
Måns Jonasson, I should say that we really do appreciate this plugin and can't find anything out that accomplishes the same task. This is something that people should be aware of as they move forward... and if what I described is not actually the cause of the issue, please let me know.