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.