Headset for Lumia 720

The most vague criteria is anything that is not for iPhone/iPod/iAnything

Those will certainly not work. Otherwise, I've heard of people using stock Samsung ones, I'm partial to the noisehush ones I picked up in the WC store.