According to Verizon, at least, you should not install/remove the SIM with the battery in. Also, every picture I've seen of a SIM card has the text 'do not install with battery in phone' or similar.
I think that the SIM card standard wasn't built with hot-swap in mind. This may be one of those things that you can get away with, but if it wasn't made for hot-swapping, then it's likely that there's going to be trouble if you try it. The question is - does phone off and battery in count as hot swapping?
Edit - I had been thinking that one should remove the battery because I don't know if the SIM gets any standby power. But Eric's comment below reminds us that some phones have fixed batteries, and therefore it MUST be safe to insert/remove the SIM in at least these phones with the battery installed.
I'm still going to pull the battery whenever possible for doing SIM swaps, but since I only swap SIMs once every never, it's hardly a hardship for me.