MSAA is heavy specially at 16x because is more or less a type of super sampling (rendering the scene at higher rez than displayed), but unlike the later is way faster, but like SSAA, MSAA still increases pixel count.
Yes i'm not surprised AA was the main culprit good it was not something else.
Btw Stencil shadows are mostly CPU based, shadow maps are GPU based and because you were already GPU bound, changing to to maps wouldn't make any diference, perhaps even make it worse, because maps are normally slower than stencil, thou today because of some exclusive effects to maps, I would recommend them to everyone.