There are frequent fliers, and then there are people like Steven Rothstein and Jacques Vroom.

Both men bought tickets that gave them unlimited first-class travel for life on American Airlines.

Passes in hand, Rothstein and Vroom flew for business. They flew for pleasure. They flew because they liked being on planes. They bypassed long lines, booked backup itineraries in case the weather turned, and never worried about cancellation fees. Flight crews memorized their names and favorite meals.

Each had paid more than $350,000 for an unlimited AAirpass and a companion ticket that let them take someone on their adventures. Both agree it was the best purchase they ever made, one that completely redefined their lives.

In the 2009 film "Up in the Air," the loyal American business traveler played by George Clooney was showered with attention after attaining 10 million frequent-flier miles.

Rothstein and Vroom were not impressed.

"I can't even remember when I cracked 10 million," said Vroom, 67, a big, amiable Texan who at last count had logged nearly four times as many. Rothstein, 61, has notched more than 30 million miles.

But the miles they and 64 other unlimited AAirpass holders racked up went far beyond what American had expected. As its finances began deteriorating a few years ago, the carrier took a hard look at the AAirpass program. Heavy users, including Vroom and Rothstein, were costing it millions of dollars in revenue, the airline concluded.

The AAirpass system had rules. A special "revenue integrity unit" was assigned to find out whether any of these rules had been broken and whether the passes could be revoked.

Rothstein, Vroom and other AAirpass holders long had been treated like royalty. Now they were targets of an investigation.

Unlimited passes

When American introduced the AAirpass in 1981, it saw a chance to raise millions of dollars for expansion at a time of record-high interest rates.

It was, and still is, offered in a variety of formats, including prepaid blocks of miles. But the marquee item was the lifetime unlimited AAirpass, which started at $250,000.

Pass holders earned frequent-flier miles on every trip and received lifetime memberships to the Admirals Club, American's VIP lounges. For $150,000 more, they could buy a companion pass. Older fliers received discounts based on age.

"We thought originally it would be something that firms would buy for top employees," said Bob Crandall, American's chairman and chief executive from 1985 to 1998. "It soon became apparent that the public was smarter than we were."

The unlimited passes were bought mostly by wealthy individuals, including baseball Hall-of-Famer Willie Mays, America's Cup skipper Dennis Conner and computer magnate Michael Dell.

Mike Joyce, of Chicago, bought his in 1994 after getting a $4.25 million settlement after a car accident.

In one 25-day span this year, Joyce flew round trip to London 16 times, a retail value of more than $125,000. He didn't pay a dime.

"I love Rome, I love Sydney, I love Athens," Joyce said by phone from the Admirals Club at John F. Kennedy International Airport in New York. "I love Vegas and Frisco."

Rothstein bought his AAirpass in 1987 for his work in investment banking. After he added a companion pass two years later, it "kind of took hold of me," he said.

He was airborne almost every other day. If a friend mentioned a new exhibit at the Louvre, Rothstein thought nothing of jetting from his Chicago home to San Francisco to pick her up and then fly to Paris together.

In July 2004, for example, he flew 18 times, visiting Nova Scotia, New York, Miami, London, Los Angeles, Maine, Denver and Fort Lauderdale, Fla., some of them several times. The complexity of such itineraries would stump most travelers; happily for AAirpass holders, American provided elite agents able to solve the toughest booking puzzles.

They could help AAirpass customers make multiple reservations in case they missed a flight, or nab the last seat on the only plane leaving during a snowstorm. Some say agents even procured extra elbow room by booking an empty seat using a phony name on companion passes.

"I'd book it as Extra Lowe," said Peter Lowe, a motivational speaker from West Palm Beach, Fla. "They told me how to do it."

Vroom, a former mail-order catalog consultant, used his AAirpass to attend all his son's college football games in Maine. He built up so many frequent-flier miles that he'd give them away, often to AIDS sufferers so they could visit family. Crew members knew him by name.

Creative uses seemed limitless. When bond broker Willard May, of Round Rock, Texas, was forced into retirement after a run-in with federal securities regulators in the early 1990s, he turned to his trusty AAirpass to generate income. Using his companion ticket, he began shuttling a Dallas couple back and forth to Europe for $2,000 a month.

"For years, that was all the flying I did," said May, 81. "It's how I got the bills paid."

In 1990, the airline raised the price of an unlimited AAirpass with companion to $600,000. In 1993, it was bumped to $1.01 million. In 1994, American stopped selling unlimited passes altogether.

Cable-TV executive Leo Hindery Jr. bought a five-year AAirpass in 1991, with an option to upgrade to lifetime after three years. American later "asked me not to convert," he said. "They were gracious. They said the program had been discontinued and if I gave my pass back, they'd give me back my money."

Hindery declined, even rebuffing a personal appeal by American's Crandall (which the executive said he did not recall). To date, Hindery has accumulated 11.5 million miles on a pass that cost him about $500,000, including an age discount and credit from his five-year pass.

"It was a lot of money at the time," Hindery said. "But once you get past that, you forget it."

In 2004, American offered the unlimited AAirpass one last time, in the Neiman-Marcus Christmas catalog. At $3 million, plus a companion pass for $2 million more, none sold.

Looking for cheats

Bridget Cade started in American's reservations department in 1990. In 2007, she was promoted to the elite revenue integrity team, charged with rooting out passengers, travel agents and others suspected of cheating the airline.

Her first big job was to investigate AAirpass users.

In September 2007, a pricing analyst focused the airline's attention on how much the AAirpass program was costing, company emails show.

Cade was assigned to find out whether any AAirpass holders were violating the rules, starting with those who flew the most.

She pulled years of flight records for Rothstein and Vroom and calculated that each was costing American more than $1 million a year.

Rothstein, she found, sometimes would pick out strangers at the airport and give them surprise first-class upgrades with his companion pass. Once he flew a woman he'd just met in New Delhi to Chicago, a lift American later valued at nearly $7,500.

There was nothing in the AAirpass terms prohibiting that, but Cade considered the habit striking in light of something else she found. Rothstein made 3,009 reservations in less than four years, almost always booking two seats, but canceled 2,523 of them.

To Cade, this was evidence that Rothstein reserved flights he never intended to take. It also allowed him to hold seats until the last minute and offer them to strangers, she said later in court depositions. Cade decided it was fraud and grounds for revocation.

On Dec. 13, 2008, Rothstein and a companion checked in at Chicago O'Hare International Airport for a transatlantic flight. An American employee handed him a letter, which said his AAirpass had been terminated for "fraudulent behavior."

He apologized to his friend and filed suit in Illinois three months later.

Vroom's travel history told a different story, Cade found. Time and again, he booked trips with people he'd never flown with before, traveling round-trip to Japan or Europe without even staying overnight.

"We suspect he is selling his AAirpass companion tickets," Cade wrote in a February 2008 email. That, she later said, was against the rules.

She decided to try to catch him in the act.

Checking Vroom's bookings for first-timers, Cade came across Auyon Mukharji, a recent college graduate abroad on a music scholarship. He was to fly from London to Nashville, Tenn., with Vroom on July 30, 2008.

Working with airline security, Cade hatched a plan to confront Mukharji at London's Heathrow Airport, challenging him to admit he had paid Vroom.

At check-in, American agents detained Mukharji and escorted him to a private office. A former New York police detective working in American security offered a free ticket to Nashville if he'd confess to giving Vroom money.

But Mukharji insisted he hadn't, and American ultimately released him and gave him a coach ticket home. He could not be reached for comment.

Vroom landed at Heathrow that morning. As he boarded American Flight 50 from Dallas/Fort Worth to London the previous evening, security officers took note of the clothes he was wearing, down to the Crocs on his feet.

Vroom headed for the VIP lounge at Heathrow, where an American employee handed him a letter and said he never could fly again on the airline.

Vroom was shocked. He told the airline he had met Mukharji through a friend and, because both had attended Williams College in Massachusetts, simply offered him a ride as a friendly gesture.

With Mukharji insisting he had not paid for his ticket, Cade and her team began tracking down other Vroom flight companions.

In one instance, an American security agent called Sam Mulroy, a Dallas personal trainer who had been set to fly with Vroom to Europe, and told him his trip had been canceled. The agent promised a first-class ticket if he admitted to paying Vroom, according to company emails and correspondence.

When Mulroy refused, American froze his frequent-flier account, offering to release it in exchange for details of payments, the documents show. Mulroy complained to American and the Transportation Department that he was being "extorted [in] an effort to punish another customer." He did not respond to requests for comment.

Weeks later, American sued Vroom in Texas state court. Vroom countersued.

In discovery, company lawyers tracked down a Dallas woman who had cut Vroom a $2,800 check to fly her son to London. An elderly couple gave him $6,000 for a trip to Paris. And bank records showed more than $100,000 in checks to Vroom written by owners of a local jewelry store who frequently flew with Vroom.

Vroom admits to receiving money from some flying companions, but says it was usually for his business advice and not payments for flights. Other times people insisted on paying him, he said.

Cade wasn't done. In early 2009, the phone rang at the home of Willard May, the former bond broker who openly sold his ticket when he was forced out of work. His AAirpass, too, had been yanked.

"I never tried to deceive American," said May, noting a 1993 Dallas Morning News article that quoted him and an American official about the practice. Still, he didn't make a fuss when the call came. He'd grown tired of flying.

His lawyers say the seat-selling accusation is moot because his contract didn't prohibit it; American didn't ban the practice until three years after Vroom bought his pass.

Rothstein also denies committing fraud, saying his contract did not ban multiple reservations.

Last summer, an Illinois federal judge ruled he had violated the contract by booking empty seats under phony names, including Bag Rothstein. American had acknowledged years earlier that "airport personnel have become complacent" with the practice, court records show, and Soter planned to appeal. But that case and Vroom's were thrown into limbo when American's parent company, AMR, filed for Chapter 11 bankruptcy protection in November.