GPS. Which is how they find out about your speeding, too.
Even if you are returning to the same place, make sure you mention to the rental company where you plan to go. Some have restrictions on where their cars can go or where the insurance is in effect. Again, this is particularly true of Enterprise. Just make sure the contract agreement doesn’t have a paragraph that specifies a state. If it is so, it should be a blank for the staff to fill in your presence and that you have to initial, so they can’t really sneak that on you. Still, it doesn’t hurt to ask.
The area you are going is just amazing. We went there for our honeymoon. Do not miss the Carlsbad Caverns. Worth the detour if they are not on your current route.
Shawn, Monument Valley is great - but if you guys get an SUV, you’ve got to explore the Canyonlands/Moab area. Get a good map that has all the jeep trails listed. As I mentioned, they are county maintained roads all over the place - while most of them are actually 2WD (high clearance) the 4WD will give one peace of mind. But the offroad stuff is really extraordinary. Grand Canyon is great, but one can’t drive around in it. The Canyonlands area is almost as spectacular but has an extensive network of good dirt roads through it.
Second this. Did it in November 2005. The Expedition was loaded with a lot of fragile, household goods, so my wife prohibited me from going down the mining road in Canyonlands, but the rest was fun!
I don’t know how intently they use that. Last summer we rented from them for a personal trip. Got the “border states only” schpeil and so on.
Drove all the way out to Cheyenne from Milwaukee, then headed to Billings and finally home via driving across North Dullkota, and averaged well over 90 in some spots. Never heard a word about it.
I’m thinking a way for them to find out you crossed borders would be if you had an accident, or got a photo radar/red light camera ticket that got sent to them while you were the renter.
I think some rental companies like Enterprise may have some privately owned offices so they may have their own restrictions that you wouldn’t get if you rented from one of the company owned offices.
I got flat-rate miles on a mini-van, which I would have otherwise had to pay mileage on, by using a Priceline “auction-style” rental.
Shop around. Try Priceline. Try Kayak.
Edit: And remember, their vehicle types are always lies. Their large is your mid–sized, mid-sized is intermediate, their intermediate is compact, and their compact is sub-compact.
A friend rented a Winnebago type vehicle for a big trip a few years ago. I remember it sounded costly, but he had very few motel fees, plus they took/cooked/ate their own food.
Thanks for all the input. I want to discuss some more about the Grand Canyon and environs, so I posted a new thread in MPSIMS: http://boards.straightdope.com/sdmb/showthread.php?p=8503140#post8503140
I rent a car about 3 days out of every week. Mostly Hertz, but I’ve had my adventures with other companies. Here are my thoughts:
- If you are not going to return to the location from which you rented there can be a substantial penalty–you could be thinking you have unlimited miles but it turns out there is a per mileage charge if you return to a different location. Check with the exact location from which you are going to rent as this policy can vary among locales even within a parent rental organization. It is 1550 miles from New Orleans to the South Rim. You don’t want to get stuck with a mileage fee.
 - For the best rate, try online with the company site, or online with a site such as Hotwire. With Hotwire you will not know from whom you are renting so only use that if you know your dates and if you are returning to the pickup location. In general a car is a car. Weekly rentals are cheaper than the total of daily.
 - For a long trip, consider AAA membership.
 - For insurance: check with your own car insurer to see what’s covered. Check with your Visa to see if they cover what your own insurer does not.
 - Try for a deal on an upgrade at the rental counter when you pick up. First see what they offer you. If they are out of what you rented they will give you an upgrade free. If they don’t give you a free upgrade try to find out what kind of deal is available that day, as inventories vary and they always want to move whatever car is in excess that day.
 - Don’t assume a 4WD will be available in any locale where they are in demand. Reserve that type of car if it’s critical.
 - Nothing to do with rental per se but if I were going on a trip that long I would rent at least a minivan or similar. Just a personal preference. Sedans get a titch cozy over long miles. Conversion vans are also rentable, but usually very pricey and priced per mile.
 - One thing more: if you only need a 4wd for one day, don’t rent it for all 4,000 miles. Rent it locally for that day.