If I had to guess, they probably started the project with the open source android music player, and thus inherited this bug.
*******n player on the market, and also Queek shuffler do this correctly, so it has nothing to do with APIs. I currently use *******n for everything, but I would love to use winamp on my phone just like I use winamp every day... but only if Winamp is going to behave like Winamp.
I have actually looked through the source code of the default open source Android music player and found the code at fault -- the original programmer somehow thought this was appropriate behavior and intentionally coded it that way. Why he thought this was desirable behavior I cannot speculate, and COUNTLESS programs have inherited this behavior as a result of using the Android Music Player as a base of code.
However, again, this is not an API issue. Apps handle shuffling themselves. It's a pretty easy fix too. If I recall, the playlist "array" has the last element popped off when the user hits "previous", and the song is returned to the "unclaimed pool of songs" that are randomly selected from when the next song is needed. From a programming aspect, it shouldn't be difficult to fix at all.
The only question is... is anyone listening?