Действительно ли возможно использовать один подстановочный субдомен и для сети и для входящей электронной почты?

Of course this is doable. The two protocols operate on different tcp ports, so when a browser is opened and pointed to random01.example.com, it's hitting your machine on port 80, and when a user emails user01@random01.example.com, it goes to whatever the MX record is in your DNS, and if that's the same machine as the webserver, it's on a different port (25).

The question of the DNS for that hostname is irrelevant. You can have random01.example.com point to your webserver IP, and mail will still work, because mail relies on the MX record in your DNS, so for all you care, you can point the MX record to a completely different domain (like google mail's service even) if you wanted to.

Say for instance your webserver is 1.1.1.1 and your mailserver is 1.1.1.5

The hostnames would be:

*.example.com IN MX mail.example.com

*.example.com IN A 1.1.1.1 (webserver)
mail.example.com     IN A 1.1.1.5 (mailserver)

And voila... people can hit random01.example.com on the web, and mail to that domain also goes to the correct mailserver.

edit: I'm using those lines as I'd probably write them in BIND. How you'd set that with your nameserver I don't know, but it should be straightforward stuff to add A records, and add an MX record that points to an existing A record. What I have found is that Zerigo accepts "*" for wildcard hostname entries in its UI.