Since your usual DNS queries are non-wildcard, your only options are:
- ask politely for the whole list (aka zone transfer or call the admins - i.e. that what you wanted to avoid)
- settle for an incomplete list
Hacking the server and just getting the config file usually is not an option, neither is eavesdropping on the zone transfers to the secondary/backup servers. Apart from those, there is no instance knowing all possible subdomains.
Options for getting incomplete lists:
- send random queries (aka bruteforce, though you won't get very far - but perhaps some dictionary-style guessing might help you nonetheless)
- ask google, using the "site:example.com" filter
- use your own crawler to follow links, hoping that all subdomains you might be interested in are linked somehow. You'll probably miss smtp.example.com, though.
Also keep in mind some zone files do have wildcards themselves, so *.example.com might give you the address(es) of a web dispatcher configured to handle web1.example.com, sales.example.com, etc. differently. This works with all protocols which use the hostname not only in the IP-level but also in the application data stream. (e.g. name based virtual hosting for http)