Hmm.
If you want to the skylight-effect, there's no way around using lots of rays.
Blender supports another method that is fast and noise-free but I reckon it doesn't work well with low vertex-density.
Try Mentalray with fewer samples or lower lightmap resolution.
Skylight/Ambient Occlusion in general does not need a high resolution, unless you have loads of tiny details.
I really would like to see a sample of your baked objects, because I do not believe you that there's no more room for optimization.
