The first thing you need to do is ask what value you would be to the airline.

As a general rule of thumb, you won't get anywhere unless you:
a) Consistently buy full-fare tickets.
b) Consistently fly in first(US) business(Europe) class.
c) Make at least 8/12 flights a month (on one airline).

If you meet all of these, then send your last 12 months statements (for only one airline) to the Marketing Director of your chosen airline along with a letter saying why you would fly with the new airline instead of the old one and confirming that your 'flight-patterns' have not and will not changed.

Think carefully about when you do this, it is a one-off chance. The airline will expect you to attain the elite level they have comped you to the next year.

Many airlines 'flag' passengers who are comped to Elite status and (although they would deny it) don't offer the same level of service. If you are comped and use the "I use your airline alot" argument to get something it won't work.

The airlines will also want to know the deatils of your travel agent/travel arranger, who they will contact to confirm your flight patterns.

Make sure the routes you have listed on the statement you send the new airline are ones they serve. They won't comp you if they don't serve the routes you use.

If you are an Executive also send a Business Card, most airlines take into account your position in the pecking order when comping. The argument being it would be inappropriate to comp to Elite a junior officer and not a VP. The airlines will also check this with your travel agent/arranger, who may well say "this person is inappropraite for Elite".

If your employers have any kind of corporate travel function or agreement with the airline, they will almost always have an agreement whereby only the most senior execs get comped, you are therefore stuffed.

My advice is don't bother unless you are really hacked off with your current supplier and your business is clearly attractive to another airline. If you are flying First/Business anyway what are the benefits, why not earn the status?

If one of the attractions is 'upgrade certificates', bonus miles etc. don't bother, you will only get what you earn as a comped Elite.
MF