It is First-In-Last-Out algorithm.
This is because what you actually lose is Character Level, and Character Level is basically a count measuring your power. When you lose a Character Level, your power decreases, but you are the same character as you were one level-up ago, when your power was lower.
In other words, when you gain or lose Character Level you can't change choises that you have made for previous Character Levels.
You just kind of become less "experienced" once again. If you have lost one level you only lose a feat if it was gained last time you leveled up. You can't just pull the level from the middle of your progression. In case of skill points it is awesome if you keep track of what ranks you picked at each level, in case for you to be able to roll back one or more levels.
One shouldn't be able to say if your character ever lost any levels or just never had them. The main thing here is the fact that your character should be consistent at any time. You should be able to reverse-engineer it level-by-level at any time and all prerequisites for things you do have at any given moment should be in place. One shouldn't be
As an example, check the rules for Retraining if you have access to PHB II. They are constructed the way they are constructed for a reason. When you retrain some of your previous choises, you should qualify for the thing you choose anew with only those things that you were able to get prior to the choise. So, once you retrain something it is impossible to say if your character ever lost anythat something was retrained.
If you'll let people pick what levels they are want to get rid of, you'll be faced with numerous issues concerning prerequisites, like so-called early entry becoming trivial or just never had themcharacters risking to stack with unusable stuff.