I, too, had this problem, and found a simple solution: Avoid Audible Format 4. For some reason (probably related to its new bookmark system), format 4 will jump around, even if you take steps like pausing and shutting off the Shuffle quickly. But format 3 has fewer issues. In fact, in iTunes, I often queue up the exact place I want to resume a format 3 audiobook, then I sync up. When I turn on the iPod and push play, I'm right where I wanted to be. Not always, but much more often than not, and in the very few instances of jump, I'm not as far ahead or behind as format 4 will put me. But where format 3 really comes in handy is in its shut off. Turn off the iPod Shuffle with format 3 and you'll start up where you left it. You can't beat that.
There is a setback to format 3, however, and that's its reduced lack of sound quality. It's just not as rich as format 4. But then again, you won't be searching all over the place to find where you left off, and you'll save loads of MBs. So give it a try.