Outstanding advice. As a self-taught Maya user, I have never understood the different lights, but this explaination was easy to understand and very accurate to my situation as well. Thanks Much.
This answer dates back to 2010; a lot has changed since then. I've gotten very good results using physical area lights, which use a MILA light shader and a brute-force final gather. You can size the area lights up pretty big - the larger the area the softer the shadows, in general. The render settings in Maya can be broken down to optimize different aspects of the render - if your only problem is the shadows then you can leave the "Overall Quality" at 0.25 (which always seemed ridiculously low to me), but crank up the "Lighting Quality" and you'll focus all the quality settings to the shadows. It's pretty efficient that way.
I generally test the quality settings by doubling the numbers - 2, then 4, then 8 ... then once I get the quality I need I start backing the settings off to try to reduce render time without sacrificing too much quality.
I suggest getting familiar with the MILA materials and the physical lights - mentalray is now optimized for this physical based setup.