The obvious solution would be to first calculate M for invert rotation of modelview matrix, then for each sprite do:

glPushMatrix
glTranslatef
glMultMatrix(M)
Render
glPopMatrix

I would imagine it to be equally fast.