This isn't pitched as a heavy-duty corporate solution, but SyncML is supported my most phones today. It is an open protocol that lets you sync addressbook information, notes, bookmarks, etc. with a server (and open source servers like funambol already exist). There are also sites like Mobical which offer free SyncML hosting.

Basically, here's how it works: You set your phone up to sync automatically with the SyncML server every couple days. Then whenever you add, say, a contact, it gets uploaded to the server. If you lose your phone or just upgrade, you point your new phone at the server and sync to recover your contacts. The protocol only sends updates, so it is relatively quick and bandwidth friendly. The sync is bidirectional, so you can also add contacts to your phone from your web browser (if your syncml server has a web interface).

Backing up using SIM cards is pretty inconvenient by comparison. You have to manually swap out the SIM whenever you backup, and the SIM protocol is very basic (it can only hold one number per name I believe).