OK, first thing I think of is Prozac. Failing that, and if you can't find an appropriate frequent flyer gift, I would suggest:

1. He probably reads a lot. Get a Discovery magazine and check out their recommendations for books this month. You might find some areas that he's interested in and that he probably won't find int he local book store.
2. Don't know how traditional he is about garb, but check out medical clothing...maybe a nice lab smock in an appealing color with LOTS of pockets?
3. Jewelery--bling-bling is definitely a no-no, but how about some sort of meaningful pin that he could put on his accouterments?
4. Seriously--a half-hour massage or a one-hour massage. Make SURE this is nonrefundable, as we guys often have a "thing" about this, which is ridiculous. My daughter and I reguolarly give these as gifts to mom, it is WONDERFUL and will make his week. FORGET about maincures/pedicures, this is just asking too much.
5. "Tattoos" -- You might consider something a little "edgy." Non-perm henna design on an arm or leg or something.
6. A print-out of his/your family tree. Lot of work, probably not doable due to time constraints.
7. I don't know why this is, and it's probably just my own limited experience with physicians, but they seem to be particularly fond of Jazz and/or Blues. Is there a funky club that plays the kind of music he likes? Consider a night there.
8. No-fail suggestion, however common. A gift dinner at his favorite restaurant. <<Edited to add--not a gift cert. Set it up with the restaurant beforehand, arrange for special and personal service; take care of gratuities and seating in advance>>