Strange. Soft shadows seem like they would *add* noise because they inherently require more samples to resolve clearly. In my tests here I didn't find it to really add or remove noise, just change the specific noise pattern, but it will likely add to render time in any case. Did you test your higher AA *separate* from enabling Soft Shadows? Try disabling Soft Shadows and see how it affects the output and render time (it can be tested faster in a crop area, of course).
- Oshyan