I've heard of problems like this with nVidia cards that are sometimes fixed by reverting to older drivers . . .
Also, how old is your card? If it's using straight supersampling, it's basically multiplying the cost, so 2xAA at 1280x800 is comparable work to no AA at 1920x1200.
(Also, if you have an LCD screen you might be able to convince it to use a border and display the lower-res image un-scaled - this would a) improve the look with 1:1 pixels, and b) allow you to use a higher res without stretching.)
(And drops into the 30s or even occasionally into the 20s shouldn't have too much impact on gameplay, especially since precision aiming isn't exactly a major part of this game.)