I discovered that certain settings within Bluetooth preferences and iChat preferences, amongst other apps, sometimes weren't sticking past two or three reboots.
After much thinking and playing, I discovered the answer: FileVault. Because FileVault encrypts on the fly, it apparently has a little bit of trouble with the whole preference checkbox thing. So I turned off FileVault, reset the preferences, ran without FileVault for a day, and then turned it on again. Boom, fixed.
[robg adds: I haven't yet (and probably never will!) try FileVault, so I can't confirm either the problem or the fix -- anyone have supporting or non-supporting experiences?]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20040115214721694