rebuild everything...

I guess it's nice that the Arduino IDE is getting smarter at not re-compiling things that haven't changed since the last compile...

But... Is there a way to do the equivalent of "make clean" - force the IDE to rebuilt everything regardless? (short of hunting down and deleting the .o files and .a files manually.)

Just delete the whole build directory. You get a link to it in the output window. Click the link, Ctrl-A, Delete.

You get a link to it in the output window.

Um, are you talking about the online IDE, Pro IDE, or something else?
I'm talking about the normal IDE; I've never seen anything remotely like a clickable link in the output window...
(and if I manually delete the whole build directory, it still uses the pre-compiled core that it has stashed 'somewhere else.')

just close and re-open the IDE

I believe it completely re-compiles when you select a different Arduino board. So if you are using an Uno get it to compile for a Mega (don't worry if that throws up errors) and then get it to compile for the Uno again.