1) simple regex to rule out the common typos such as 2 or 0 @, no period in the domain name, etc. I don't care about people whose domain name consists of a TLD only. Bring your nerdiness somewhere else, every other service is already rejecting your exotic e-mail address already anyway. Same for spaces in the local part of the address, etc.
2) if second level domain not in list of famous second level domains, AND levenschtein distance is small with a domain on the list (typically gmial, oultook, yhaoo,...), display a huge warning. Don't refuse if the user insists it's correct, but show a huge and red warning that blinks. Same with the TLD to detect "cmo", "ogr", "inof" etc.
3) Maybe send a validation email, now that you've ruled out a big number of potential mistakes. You won't get that many bounces. Or don't send the email if you don't need to!
I fail to imagine a scenario that wouldn't be neatly covered by this 3-step process.