"But frequent flier miles are different. You paid nothing for them, so you have no tax basis, so your entire proceeds represent taxable income. You could argue that the miles were included in the cost of the ticket and therefore you DO have basis, but since the tickets are sold for the same price to people who aren't members of the mileage program, you'd probably lose that argument."

However, everyone has the "right" to join these programs, it's their choice if they don't-and arguably their loss-so therefore we ARE paying for the miles. It's just that the people who do join get the benefits and those who choose not to don't. Kind of like using coupons at the grocery store-they are available to everyone and they are not considered income even though you are paying less than those who don't use them.