Basically, I want a 2D scrolling level ranging from something like 10x10 to 20x20 screens in size. The rub is that I intend to make the walls and foreground scenery totally destroyable. My plan for this has always been to create a huge persistent damage bitmap, showing where the remaining solid ground is, and use that to stencil the graphic tiles (and also to run collision detection on). The Worms games do something like this, though I get the impression that holes are punched directly into the graphical bitmap, as it isn't that big. Would it still be a good idea to run a tiles/tilebrush engine with my stencil, or are modern platforms capable of running the whole thing as a persistent bitmap, as in Worms?

 Also, as I'm a novice in XNA, I'd be very grateful if anyone can point me in the direction of some decent 2D graphics tutorials. I'm particularly interested in possibilities for combining 3D models with my 2D backgrounds, and also zooming in and out.

EDIT: also, reading your post again. You could possibly break it up even more. Into say 128x128 tiles. Then when you want to apply damage or check collision, get all the tiles within a certain radius and check against those. That might help you do much less brute force work by not using those huge textures. The only problem is that with xna, I don't know how you would be able to store different instances of the same image so they could each have their own damage.

I think this article may be exactly what you are looking for.  Ziggyware also has a great selection general graphic tutorials/articles.

http://www.ziggyware.com/readarticle.php?article_id=154