Hmm, when I check F redemptions to MEX, it shows at least 2 seats on 16,19 and 21 December 2011. MEX is good value, because it is counted as North America for miles redemptions, and has usually good availability. We've used MEX in the past as well to travel to South/Central America. And it avoids the hassle of USA immigration.
Henkybaby, you seem a bit negative on CR. I don't remember paying an insurance surcharge - maybe it was included in the overall price, but that price was fairly standard for car rental. By the way, if you do rent a car, go for a 4x4. The larger the car, the more priority you have on the roads.
We had a great holiday there a couple of years ago, with none of the annoyances pointed out by HB, and I was there again last month without problems.