Get a lawyer, ensure it's not enforcable, then sign it.
If you're in CA, sign it. If you're in MA and there is no garden leave clause, sign it. Then do what you want.
When a hiring company asks if you have a non-compete, specify: "I am not bound by an enforceable non-compete". If they ask for specifics, explain and mention the law firm you consulted. This has always worked for me.
I suppose you could also just say you're not bound by a non-compete, and leave it at that, as that's also not a lie. If I sell myself into slavery in the USA, then I can -- without lying -- tell everyone I'm definitely not a slave. Because I'm definitely, absolutely, not. Non-competes are no different: if it's prime facie unenforceable, then you are NOT bound by a non-compete, full stop, end of story. But I like to be a bit more up-front.
> If candidate A and B have very similar skills and experience and A has a non compete and B doesn't, why would anyone bother with A?
I've admittedly never been in this situation -- at least as far as I know -- because my skill-set is pretty niche (ie, I am pretty sure that I have always known all the other people in the world who are interchangeable with me for a particular position when I get to the stage of negotiating the offer).