Added Destructors to my custom classes to see if they were being called. They weren't. I wonder why GC isn't kicking in.

Finally figured out an easy fix. Implemented IDisposable on GameObject and call Dispose() right after removing object from arrays. Probably not as elegant as a resource pool, but I can't guarantee all projectiles will be identical in the future. Regardless, my ship can now repeatedly fire 300 projectiles a second without crashing the game after any period of time (although with tremendous slowdown if firing from the bottom of the screen).

Thanks to everyone who helped, I really appreciate it. Moral of the story: IDisposable is your friend. Well, sometimes anyway.

Cool, may I ask you how you use the Console.WriteLine in your xna game? I didn't even now that it was possible, but it seems to be a great way to debug

A very easy way to use reuse resources is to make the index you want to remove unuseable (set it to null, add a flag, or whatever works for you).
At the same time, push the index to an array/list/vector that will hold all the "free" indices.
Now each time you want a new object, check first if you have a reuseable index, and if so grab it (and remove it so it wont be used again) and fill the object at that index with your data.

It sounds like the original object you are creating still has an existing reference somewhere, which is the real problem. You'll probably still run out of memory just at a much later time now that you are getting rid of most of the object's stuff.

Where do you call Create and Destroy?

Cool, may I ask you how you use the Console.WriteLine in your xna game? I didn't even now that it was possible, but it seems to be a great way to debug

Yeah, it shows up in the Output window after the startup messages finish. By default that won't show up in the editor unless the game is running, so you have to enable it if you want to check it afterwards. Can't remember off the top of my head exactly which checkbox you need to hit, but Google will give you an answer there.

@Way2Lazy2Care
For now, Destroy is only called in Projectiles when they exceed the screen's bounds. Create is mostly a fancy wrapper for Game.AddObject, so if I "Create" something from Game, I'll use AddObject instead. That said, Game calls AddObject on Ship at the start, and Ship calls Create on Projectiles to fire its weapon. Could you elaborate more on the existing reference you mention? If it's a problem, it's one I'd prefer to deal with when I'm not working on other facets of the game.