I think this has the potential to cut out spam. I don't see any way for the spammers to get around it besides paying the dues. Kinda like a toll road, if you want to use the road you have to pay up.
The only problem is for the companies. Everyone likes the word free. Nobody likes to hear that they have to pay.
This is almost definitely going to push email users to google and other online mailers. For this to work it would have to be the industry as a whole saying, "things need to change and this is the way to do it." Not just two companies who stand to make millions off of it saying, "this is how its going to be like it or not." I would accept it if it became an industry standard.
But then spam wouldn't be an issue if people just learned how to keep their emails private.