Interestingly, Microsoft is one vendor that says you can not virtualize Home editions of the Windows Vista operating system. That's not unexpected given the audience they intend it for (home users).
Other software vendors tie their licenses to specific machines through machine properties or they have gone so far as to detect virtual machines: some obscure stock trading programs and niche vertical applications come to mind. These vendors are living in the dark ages.
A larger threat than licensing to virtualization is Product Activation like that which is built into Windows Vista, Adobe Creative Suite, Diskeeper, and a growing list of vendors. Some of these trigger on basic machine changes like RAM size or Ethernet MAC address. Where activation is sometimes enforced every six months (Vista), deployment in virtual machine can trigger every time creating usability issues.
Like Jackie says, Surgient has a set of Best Practicies that avoids scenarios that don't work or we have working relationships with a number of vendors that are aware of our solutons including Microsoft, Adobe, SAP, IBM, Oracle, HP, Mathworks, etal.
In addition, VMware's own ESX Server is licensed through FlexLM so we're very familiar with how to monitor and manage capacity utilization of these kind of licenses.
Hope this helps -