I was under the belief that the fee was charged based on when you made your reservation, not when you fly--in other words, if you booked a ticket on 1/31/02 to fly on 2/1/02, you did not pay a fee (the fee came into effect on February 1), but if you walked up to the ticket counter on the first to buy a ticket for the same flight, you would have had to pay the fee. See http://www.dot.gov/security/fedreg122801.html ("Direct air carriers and foreign air carriers must collect the security service fees on air transportation sold on or after February 1, 2002"-emphasis added).

However, if for some reason an itinerary that was booked before 2/1/02 was changed after 2/1/02, you would then be charged the security fee (this happened to me with a reward ticket on CO for which I wanted to change the dates).

Old Gold--my guess is that it would be difficult to try and avoid paying this fee (CO will argue that it is a government fee that they have no control over), but you might try to counter-argue that (a) it was not a change you made, but that CO made, and (b) in reality there was no change at all. Good luck with this.