Tony - try a custom shuffle based on LRP, but without any random element. Report what you find.

I've noticed that a lot of my tunes have 2 last_played fields:

2405 36e0 Thru\ Metamorphic\ Rocks:
type = tune
last_played = 1008094024
skip_count = 0
play_count = 2
drive = 0
length = 16717802
title = Thru Metamorphic Rocks
PlayCount = 2
SkippedCount = 0
LastPlayed = 1008094024
year = 1979
artist = Tangerine Dream
genre = Instrumental
source = Force Majeure
codec = mp3
bitrate = vs153
offset = 0
samplerate = 44100
duration = 872168
tracknr = 3

Maybe yours do to, but aren't identical as mine are?