I lost a Logitech bluetooth headset, as you say, too small, who knows where it went.
That's why I ended up with a Cardo Scala 500 headset. It has this ingenious little eye-hook that slots into the charging-plug hole on the headset: The eye-hook is connected to a lanyard that you wear around your neck (or that you hang wherever you want, on your backpack, briefcase, whatever) and that makes it a lot harder to lose. Works great, and has wonderful wind-muffling built-in.