Soldier quality is influenced by a few factors (see my question here), some of which you can directly influence. As you progress in the game, enemy soldiers will tend to have higher skill rankings. You can quickly spot skilled soldiers by scanning everyone you meet - you can even interrogate enemies and they might reveal the location of a specialist. Finally, you can get higher rated volunteers by having a high amount of heroism, but I haven't seen any S+/S++ recruited this way.
Now, how can you specifically get the best of the best? Well, S and S+ soldiers can be bought with PF grade points. These can be definitely earned through the PF virtual league (you do simulated battles against other PFs - success is based on your combat, security, and research ratings), and probably through other means (but I can't confirm any). You can also kidnap S/S+/S++ soldiers from a rival's FOB, but this may prompt retaliation from them.
Finally, on the question of the game "demoting" soldiers: This is possible. One of the abilities soldiers can have is "boaster" - your goggles will overstate their abilities. It's usually only by a level or two in my experience, but I've heard some reports of it being by more than 2 levels. Be cautious about any "boasters" you extract - they won't be as good as they said they were.