There is nothing in writing saying we don't get miles on any airline. There were rumors saying that we didn't get them on American when I got hired, but I have been unable to find anything from FedEx that said that. There are no FCIFs on file, and nothing in the FedEx intranet that says we can't accrue miles on any airline.
The individual airlines do have limitations, usually government fares, or other specific restrictions; however, that also doesn't apply, as the airlines have always taken a frequent flier number on every flight I've taken. I was an elite member on American long before that memo came out. As far as I could find in talking with the travel folks, is that their reservation computer had difficulty adding a frequent flier number, but you could always have the airline add it at the gate, or do it online through the airline's website.
There are, however, straightforward restrictions on hotel loyalty programs. Mainly they state that airline rates are exempt from accrual, except for incidentals, and hotels where we have point accrual negotiated.