Methods, systems and computer program products for deploying a virtualization system onto cloud computing infrastructure. Virtual machines of a virtualization system are deployed onto computing nodes that are interconnected via a cloud provider's networking infrastructure. When migrating a virtual machine from a source computing node to a target computing node that is also interconnected to the cloud provider's networking infrastructure, the addressing of the to-be-migrated virtual machine changes. Dynamically-updated media access control translation tables are maintained at the computing nodes. The media access control translation tables are populated with cloud provider media access control addresses received from the cloud provider. A virtual switch at each computing node modifies incoming and outgoing packets of a to-be-migrated virtual machine based on contents of that node's media access control translation table. On an ongoing basis, addressing information for migrated virtual machines is received at the computing nodes by operation of address resolution protocols.