They say up front that email validation is hard, and yes there are tons of edge cases and obscure tricks and rules and probably there's no guarantee that even they managed to get it right with this service, but ultimately the customer either puts in the correct address or they don't. If they're going to make a typo then it's far more likely that it would be a legal typo, and if they're going to intentionally enter a false address then it's likely it'd be a simple asdf@asdf.com.
Edit: This was a bit of a knee-jerk reaction to what I at first saw as a redundant overcomplication, however as russjones points out below it has already proven its value in reducing bounce rates by a significant percentage.
So, it might not fit my own limited use cases, but it certainly can't be ruled out entirely. Best of luck to the Mailgun team and I hope people smarter than I am can put this service to good use.