Wildcard DNS, two solutions, which one?

Hy, I got a domain (say example.com) and a server (say IP 1.2.3.4). I want to relay every traffic which is requested from the domain to my server. Every subdomain should be handled like this (so wildcard DNS). There should be one exception: The subdomain mail.example.com should be routed to another ip (say IP 2.3.4.5)

My previous hoster made the following zone-file for the dns server for me:

@                        IN A       1.2.3.4
mail                     IN A       2.3.4.5
*                        IN CNAME   @

Now, my new DNS-Hoster claims this is invalid and proposes this new zone file to me:

@                        IN A       1.2.3.4
mail                     IN A       2.3.4.5
*                        IN A       1.2.3.4

Is the first one realy wrong? Is the second one correct and does what I want?

I already read I a Wildcard CName DNS Record Valid, so the first one should not be wrong but only unsuported.

Thanks!