Xbox 360: now powered by a hamster spinning a wheel

We've been trying to track down and smooth out some weird performance issues. With some things, C# makes the Xbox 360 run worse than my old Apple IIe. Our game runs quite smoothly, except when something has scrolled down out of game world bounds and needs to get taken out. Then it snags. Well, ok, it's not just anything, it's only enemy ships, but they're no different from anything else. Everything's in a hash set, so chopping them out should be just as cheap as adding them, but adding them is smooth and removing them sucks. Remove 20 ships? Yup, that can cost you a good fifth of a second apparently. Wtf.