That said, turning vertex buffer support back on still only got me to 40fps for a 500x500 map in Sir Boingers. In that case the animated tiles were to blame--every time a tile changes the map needs to be recalculated. But I think I have a clever way to get around that.Sorry about the performance regression--this is actually kind of embarrassing.
My idea was quite different: I have the tileset loader create two images, one for the original atlas, and another which is used as the texture for actual rendering. When the tileset is loaded, the texture is a perfect copy of the atlas. When a tile animates I use render-to-texture to update the texture image by blitting the proper tile from the atlas.
edit: Actually... that gives me an idea! Rather than creating one large triangle strip for an entire map, I could slice it up into screen-sized rectangles and only draw the slices which are actually visible. If we assume a 320x240 screen with 16x16 tiles (or equivalently, 640x480 with 32x32 tiles), each slice would be 20x15 tiles, or ~1500 vertices. In the worst case we have to draw 4 of those, so that's 6000 vertices--which remains constant regardless of the overall size of the map and is quite a bit less than a million!