I check if there's indeed a mail server in DNS to avoid the hassle of waiting for potentially slow SMTP servers to respond - for most cases, it works and I end up catching bogus email addresses from the domain names themselves.
A MX record is not necessary for a host to be able to receive email.
Note that that library can also check for an MX server. It goes Valid string -> MX exists -> User exists (you can choose to only check for MX, or only for valid string).
Really? How is mail routed then?
It should fall back to a A record. That's not exactly best practice, but if you're compliant that is something that you should be able to handle.