I think that's it! I've been wondering why Bash sometimes deletes most of my history for ages. My .bashrc sets up an EXIT trap that git-commits my history, so I just looked at the commits that remove lines and found that 7 out of 8 of those commits change the size of the history file to about 1000 lines. Since my history file contains timestamps, that matches the 500-command default of HISTSIZE, so the truncation mechanism you described seems to be what's happening.

A few days ago I actually made my history file append-only to prevent truncation.