The problem comes when spammers forge From headers which leads to:
-1: Very many emails in the greylist everyday
-2: False positives if they use a From that you've previously accepted (ie that person gets infected)
-3: False negatives if you get a spam that you reject which was sent from an address that you really want whitelisted.
Some of the failure modes are similar to challenge-response systems.
Nothing stops you from doing greylisting today, and it can be a very effective means of stopping most spam. There are tons of software solutions for greylisting.
Some require manual approval first time. Some sends a message back to ask the sender to do something (anything from just clicking a link to entering a captcha) and relies on you to do manual approval now and again (to catch automated but valid messages).
Some just defers delivery and waits for a second delivery attempt (because most spammers practice "fire and forget" and just ignores errors). Our office mail server is in the latter category - first time someone e-mails us,a second delivery attempt needs to happen after 10 minutes for the message to get through (it's ok if there are attempts in between too, but the assumption is that most of even the few spammers that retry will go away too quickly to send another attempt after 10 minutes). It gets rid of the vast majority of our spam before our real spam filter even kicks in.
Also, considering how easy it would be to spoof "x", they could probably make people click "yes" a significant amount of the time.
- the spammer has just succeeded in putting their message in front of you. If you had 500 of those per day, it would constitute spam which would again need the same filtering.
How does this prevent me from getting a certificate for "Viagra Salesman" or even "Roger Smith" and sending spam selling viagra?
Whilst I don't generally believe governments should intervene in the internet, this is one area they could intervene in. They could act as a certificate authority.
Of course, CAs will make mistakes, but they can revoke certificates when things go wrong.
This is already how we manage to block most spam on the edge. What you're proposing is just a small iteration on the existing defences. An expensive one, which wouldn't work unless you managed to get everyone doing it at the same time.
However, this isn't necessary for all communications. For instance, if a communication is signed by a reputable company (bank, for instance), then don't bother asking. ISPs should keep the list of reputable companies as short as possible and, regardless, it gets rid of phishing emails.