Following up on my experience with iPhone headphones, here's what I'm currently using for carrying cases. My day-to-day case is a venerable iPod Sock. Not only are they a great value (six cases for the price of one), they don't add any weight or bulk and easily stretch to hold an iPhone Bluetooth headset, too.
For airplane travel, I temporarily switch to a Belkin Crystal Case. It has a kickstand that props up the iPhone at the perfect angle for tray table video playback. Having spent many flights holding my video iPod for the entire flight, this case has been a real treat. It works as a belt-clip style case too, but I'm not sure I'd trust it to hold the iPhone securely. However, for watching video, it's superb.
For information on other cases, see this Chicago Tribune article.