I've noticed the same thing with my 396T. I only noticed the behavior above 470MHz so far. No problem searching 450-470. It's the exact same behavior you described.
I suspect the radio's PLL isn't locking up fast enough on each step in frequency as the frequency steps along. The squelch circuit could be opening too slowly, causing the search function to overshoot an active frequency and just keep going. The squelch circuit also has too much hysteresis for my liking and the extra hysteresis will tend slow down its opening/closing. (Typical Uniden design.)
The strange thing is that scanning known active frequencies it skips during search works fine if you program those individual frequencies into a group in a system.
Too bad there isn't a scan/search speed control to help test my theory. Older scanners years ago often had a selectable scan rate (fast or slow). I found it to be the most useless feature on a scanner, except for testing a situation like this with a 396T.
I've witnessed the exact same behavior with searching some frequency ranges.