Unfortunately for you, they appear to be taxable. Here is the section from IRS code for 2002:
Frequent Flyer Miles
Frequent flyer miles are a benefit provided under an airline frequent flyer program. They are also used as a promotional benefit through rental car programs and hotels.

The IRS has announced it will not claim that any taxpayer has understated his or her federal tax liability by reason of the receipt or personal use of frequent flyer miles or other in-kind promotional benefits attributable to the taxpayer's business or official travel. Any future guidance on the taxability of these benefits will be applied prospectively.

This relief does not apply to travel or other promotional benefits in the following three situations:

When they are converted to cash,
When they are used as compensation (payment for your services), or
When they are used for tax avoidance purposes.

http://www.irs.gov/formspubs/page/0,...53,00.html#T12

It seems that since these miles could be considered "compensation", you will have to pay tax (personal observation).