To be fair about (3), I think they already do that. They mention in the article that the cards are redeemed by people in your country.

Unfortunately, the gift card is an item that is intended to be easy to give to other people, just like cash. This doesn't seem like an easy problem to solve.

I think (4) has the most chance of success. Even just adding a 4 hour "activation time" on cards worth more than $250 would make the scam just a little harder to pull off, and real consumers would rarely be inconvenienced. The guy in this story would have realized he was scammed and had ~4 hours after the call to try to fix the situation.