I searched high and low for a holster for the 650. I like simplicity so I was picky. Then I ran across a blog entry (which I can't find again) where the guy had used a iPod case! My daughter had an iPod and hadn't ever used the case. This was right before Christmas so I bought her a "cool" iPod case with a hole in it for the spin wheel and a transparent window for the display. She was thrilled and I took her Apple case.
The case has worked great. It probably isn't as sturdy as some made-for-phone cases but it has been fine. I broke off the belt clip when I got in the car with it on my left hip rather than my right hip. The Apple store was on my way back to work so I just replaced it. Of course, it was pricey there but convenient.
My other challenge has been a Bluetooth headset. Frugal that I am, I jumped on an IOGear headset from buy.com for $29.95 (no longer on sale). The first one I got rattled! There was something loose in it. I exchanged it but the second one sounded like crap. I bought a Motorola H500 from the local Cingular store. I never could get the volume to be loud enough. I'd have to actually press my hand against the headset to be able to hear. So back to Cingular it went. This time I got a Plantronics Discovery 640. It is the in-ear style and it works fine.
I read somewhere later that the Treo 650 doesn't have a strong outbound signal on the Bluetooth so you need a headset that has plenty of amplification. Seems that the Motorola H50 doesn't have much amplification. I'm sure the in-ear fitting of the Plantronics 640 helps as well.