I'll tell you what I do. It's not the fastest, but it's fairly quick (as in runs ok on a 1ghz pc with a geforce 2 mx). Memory usage wasn't really a problem in my case, I just tried to keep the cpu and gpu usage down.

Firstly, I used a better algorithm to generate the shadow volumes. Not really a performance thing, more of a robustness thing, but here's a paper.

Secondly, you mentiond GL_QUADS. If that's how you're constructing your shadow volumes, then that may be your problem right there. What I do is create a vertex array for twice as many vertices as my object actually has. In the first half I put the objects vertices, and in the second half I put them in extruded in the light direction. It would probably be better to work out which vertices need extruding, but I'm not sure if that would be faster or not, and memory wasn't an issue.

Next, you construct an index array for rendering your shadow volumes. I'll assume depth fail here. First thing is the front cap. Just find every triangle in the model that faces the light and add it into the index array. Then the back cap (should fix your artifacts). Add them all in again, but this time swap the winding and offset the indices so that they point to the second half of the vertex array. Finally, the hard part, the sides of the volume. Go through all the edges that need extruding, and add a couple of triangles that make up a quad between those two vertices and the corresponding vertices in the second half of the array. Make sure the winding is such that they face "outwards".

Finally, we can draw the shadow in just two calls, once to draw front faces and once to draw backfaces. Your graphics card will thank you.

If you're actually fillrate limited, then that's a bit trickier. See if you can reliably get the shadow volumes to only go just through the ground. If you have a ground plane that's always at the same height that shouldn't be tooo hard. Also, make sure your volumes are actually optimal, and you're not treating every edge as an extruded edge or something.