I find end-users tend to think that a wireless headset is like a wireless phone (huge difference). A wireless headset is not really ment for walking around the office. It's made for very short distances, filing, faxing, coping. They are not ment for lunch rooms, breaks, bathroom, running to the car, or going to visit the CTO at the back of the office. The customer needs to understand that.
I would recommend getting a ONS cordless ($20, or less) and getting one with a headset port. That will be the cheapest, most effective solution (in my mind).