I've updated the OP to detail some downgrades to F service. If someone could find me a reference to the A333 Envoy changes so we can put a date range to those, I'll add them to the list.

I searched for the reduction of elite bonuses mentioned by Phudnik and ClueByFour, but only found this related thread that suggested this started sometime in 2006:
Still getting 100% bonus as GP

I'll add the items mentioned by ClueByFour and PHLbuddy to the OP in a moment, but don't have dates for those yet.

Facedoc - I was not aware of your #3 - do you know when that change occurred? Your #2 is difficult to prove, though.