marks, if you have a file available, upload it and i can check it for you. i do 10million+poly bakes with no problem, and max will spit out a 2k normal map in about 2-5 minutes. and about 15 min or so for a quality mr ao bake,
to address some specifics,
if your using go-z keep in mind max applies a direct x material to your hi-poly object.
i haven't tested what the result of baking with this applied is, but swap to default materials to be sure.
i would avoid rendering normal maps in mentalray, the sampling quality (more specifically the aliasing where meshes intersect) needed to match the scan line, makes its normal map renders much longer. but it is faster at low sampling rates. but generally and for consistency i always use scan line with the hammerssly sampler for nm.
for AO, i use mental ray, i just like the control and results i get, if your AO bake is going slow, try using the ao shader in the diffuse slot then just render a diffuse bake.hopefully this helps a little, and post your file if you wan't someone to look at it.