I ran every utility I could think of and tried every tip from MacOSXHints that seemed relevant: re-installed 10.3.6 from the combo updater; reset the NVRAM in open firmware; deinstalled every extras I had running -- all to no avail. What finally made it stop was creating (and logging in as) a new user. Armed with this information, I moved my main user's entire Library -> Preferences folder to the Desktop (so it rebuilt all new preferences), and low and behold, this fixed it too.
Then I added select preferences back in groups. At one point, the problem reappeared and I narrowed it down to one of the group of com.apple.finder.plist, com.apple.loginwindow.plist, and com.apple.systemuiserver.plist.
I couldn't narrow it down any further, but the problem has now been gone for a week, and hasn't come back. Hopefully this will help someone in the same boat...

