I also posted this question on the Google NDK Group: https://groups.google.com/forum/#!topic/android-ndk/rzVr3A0DjBs
While I never got an official answer from anyone at Google, the feedback I received seem to indicate that Media Player and/or playing audio from a URI with OpenSL ES is known to be buggy.
I ended up solving this problem by using a 3rd party mp3 decoder with seeking ability and a Buffer Queue Audio Player object in OpenSL ES to playback the audio samples.
Hardly easy to do, but it works.