I was cleaning out a drawer and found a horizontal pouch that I used to carry an old Nokia phone in. I tried my 7100 and it fits like a glove. As a bonus, I can see the status light and the magnets seem to trigger the auto on/off features of the phone.
I'm a big fan of these "horizontal pouches". They're great for anyone with lovehandles as they more or less follow you're belt and don't rub the old spare tire. This one has a flap over the top and almost completely covers the phone, so you can't beat up the exposed part that sticks out of the standard case.
I bought mine at a kiosk in the mall a couple of years ago. As best I can tell, this is the same model: http://shop.store.yahoo.com/eastmanw.../bysptepo.html
I'm definitely using this from now on.
Now, if I could only find a better way to carry my HS850....