Non-dot-wildcard (*-foo.example.com) for bind?

The reason why it doesn't work is because it's not defined behavior within the RFCs. It must be implemented as an extension of the software you're using. RFC4592 cements the definition of a wildcard record pretty firmly:

2.1.1. Wildcard Domain Name and Asterisk Label

A "wildcard domain name" is defined by having its initial (i.e.,
leftmost or least significant) label be, in binary format:

  0000 0001 0010 1010 (binary) = 0x01 0x2a (hexadecimal)

Note the term label here. A label is the dot separated entity. If you have anything other than the asterisk in the label, it's not a wildcard.

You're kinda stuck here. Working within DNS, you need that dot that you're trying to avoid. Everything else is extensions to the server software and implementation specific.

RFC 6125 prevents having a generic certificate for nested subdomains. RFC 4592 and RFC 1034 prevent from having *-xxx.domain.com as a DNS entry.

So you only have two alternatives (which is not nice when trying to automate) :

• Create a certificate per subdomain (there are free alternatives but might be complicated depending on your platform).
• Create a full DNS entry per sub-service (which won't be sub-subdomains).