iPhone Works With Third-Party Bluetooth Headsets
Good news on the iPhone's bluetooth support front: you do not have to buy the \$129.00 Apple headset of questionable wearing comfort. Third-party bluetooth headsets seem to be supported just as well.
We had no trouble hooking up a much cheaper, yet nicer Motorola H700 headset with an iPhone.
Apparently, headset model is one of the few things Apple decided not to lock its users into. Happy iPhoning!