Apache ServerAlias wildcard for domains (e.g. subdomain.*.com)

Apache searches for a match in the order that the domains are defined.

If I understand your problem correctly then it can be solved by defining your hosts to be excluded before the catch all host.

Example:

<VirtualHost *:80>
    ServerName excluded.example.com
    ServerAlias  something.example.com ...
    ...
</VirtualHost>
<VirtualHost *:80>
    ServerName example.com
    ServerAlias * *.example.com www.example.com example.com
    RailsEnv production
    ...
</VirtualHost>

You can use SSL cert issued just for mail.domain.com without any problem. The biggest advantage of wildcard certs is there is only "one cert to rule them all" - you don't need to manage dozens of certs.