Second Level Subdomain DNS Wildcard

RFC2818 states:

If more than one identity of a given type is present in the certificate (e.g., more than one dNSName name, a match in any one of the set is considered acceptable.) Names may contain the wildcard character * which is considered to match any single domain name component or component fragment. E.g., *.a.com matches foo.a.com but not bar.foo.a.com. f*.com matches foo.com but not bar.com.

Internet Explorer behaves in the way outlined by the RFC, where each level needs its own wildcarded certificate. Firefox is happy with a single *.domain.com where * matches anything in front of domain.com, including other.levels.domain.com, but will also handle the *.*.domain.com types as well.

So, to answer your question: it is possible, and supported by browsers.

Normally when you define a wildcard record, it will only match if no other record matches. So if you have

example.com.        A 8.9.10.11
*.example.com.      A 4.5.6.7
host1.example.com.  A 1.2.3.4

A wild card will only be matched if there is no subdomain defined. If you ask host1.example.com. it should return 1.2.3.4 and not 4.5.6.7

If this is the case, it might be that the changes haven't propagated yet. Use the dig to query your DNS server and some public server (google's is 8.8.8.8).