Backup vendors follow different licensing schemes for backing up virtual servers. Here's a sampling of them:
Symantec LiveState Recovery: On a per-system basis. One license for each instance of an operating system, virtual or physical.
BakBone NetVault: One license per client. If multiple virtual machines are being individually backed up, each requires a license. If the physical server as a whole is being backed up, one license covers the server, regardless how many virtual machines are running on it. n
CommVault Galaxy: Priced per agent.
NSI Software Double-Take for Virtual Servers: One license covers up to five virtual machines running on a single host.