It sounds to me like you aren't actually removing them. First things first, removing something from the display list is only a visual/interactive change. It is still running until you remove any references to it, being event listeners or w/e, and then you must set it to null so that garbage collection will grab it on the next cycle. If you are using flash player 10, spender is correct that unloadAndStop will work for you as they just recently created it to fix your very problem.
i just thought I should explain what is going on, because people should not only know about the fix, but why things happen.
One other suggestion, I wouldn't load these movies to stage, I would create a container sprite/movieclip to hold them, that way even if you add other things later, they are separated, clean, and easy to access through their parent (imageContainer_mc for instance).
Brian Hodge
hodgedev.com