Although this article is written about a lost iPhone, it's really applicable to all phones: Six things I learned from losing my iPhone 3G.
Be sure to read the comments as well. I'd already followed most of the recommended practices, but I hadn't checked with my home owner's insurance to ask what it would cost to insure the phone against loss. One comment mentioned their policy increase was only $10 a year, another said the deductible was prohibitive. Note that most high end phones cost about $500 to replace unless your contract is nearing its two year renewal date. (I think for AT&T in Minnesota they'll provide the new phone subsidy if the renewal date is less than 4 months away).
I didn't realize that under some conditions AT&T will mark a phone as stolen, and may be able to retrieve it if someone tries to use it with a new account.
I photographed a business card and turned it into my wall paper. Dull, but effective. I also implemented the "delete data on 10 password retries", but some of us have young children who may try to hack a phone. If you implement this be sure to have sync regularly.