For non-registrars, the main ways you can check for a domain's existence are to make a bunch of whois queries, or to make a bunch of DNS queries.

As you said, whois queries are slow, and may be considered bad-mannered. It's also against many Terms of Service to scrape whois information for spamming/marketing purposes. But in some cases there is no better alternative.

DNS queries can weed out registered domains, but won't give you information on when they expire. It also won't tell you 100% whether a domain is not registered, since domains which are on HOLD don't show up in DNS even if they're registered. Overall, DNS queries are much friendlier, but give you less information.

If you're a registrar, you already know the better ways to do parts of what you're asking; or if not, you can ask the registry in question :)

Alan