Least often played and Least recently played do in fact work the way you stated.

However, there is still a deliberate random element added to this. The "least" factor is merely a weighting amongst the randomness. If it wasn't at least somewhat random, it wouldn't be a shuffle, would it?

There is also one more factor to consider. The byte value they use to store the "recent-ness" of the track is only valid for twelve days. Meaning that anything you played more than twelve days ago is considered ripe for being at the top of the least-recently-played shuffle.

In my opinion, that is a bug. Because at any given time, the majority of tracks in my player would be equally weighted. Therefore, the least-recently-played shuffle does not work as advertised. I do not know if the empeg team shares my opinion on this matter.