No, it is not mandatory to have the any particular format for domain names. You can put almost anything you want in DNS, and companies do use all kinds of schemes.
That said, the word "hostname" if often used to mean two different things. It can mean
- The name of the computer. This can be in many different formats, including single words, full domain names, and anything in between.
- The full domain name of a computer, whether the computer does or does not have that full name set on the computer as its host name.
To complicate this, there is absolutely no reason that either of the things you mentioned in your question is a "hostname" in the first sense of the word. In fact, many places do not have a computer with the name "webmail", instead having that name point to another machine with a different name. For example, in my old office, "mail.example.com" actually could be on a machine named "mailserver2.office.example.internal". As you can see, the "hostname" in the first sense of the word is not even a publicly accessible address.
For your example of "mail.google.com", GMail actually runs on many servers (hundreds or thousands, though no one outside Google knows for sure) so there is no computer with the name "mail.google.com". Google does not publish the actual names of the servers that "mail.google.com" points to. Even when you see "googlemail.l.google.com" when you look up the where it points to, that is also not the real name of the server, but a name that points to many servers.
For example, their could be a server named "webmail01-newyork342-version1.googlemail.datacenter-newyork.google.private" which is publicly accessible as "googlemail.l.google.com". Google uses DNS round-robin, region-based DNS partitions, and IP anycasting to make all of those servers respond to the same name.
In smaller setups, it is often true that the leftmost portion of the full address is the name of the machine that you are connecting to, but that is rarely the case when dealing with any large company.