what are some possible reasons why my company's DNS server sometimes fails to resolve the host name of some of my VM's?

If the problem machines are not members of an Active Directory domain that the DNS server trusts then they will not have permission to insert entries into the DNS server.

If your company's DNS server hosts a .local domain then it will interfere with the zerconf functionality of mDNS/DNS-SD available to OSes like Windows 7.

The question Windows DNS sometimes can't pick up my VM's hostname is similar, though the problem machine is not windows based, similar issues may be involved.