I have the exact same problem. I checked all the suggestions in this post and none of them work for me. I do not use Sigil or Calibre, I write myself the OPF.
The Go to beginning is OK in Previewer and PC reader, but NOT in kindle device
I use KindleGen 2.5, Previewer 2.51 and eInk kindle firmware 4.1.0 and everything I have read so far seem to indicate it is a v4 firmware bug.
Unless I missed something here it seems there is no workaround yet. If someone has the solution with K4, please help ...