I decided to start using virtual machines for my testing. VirtualBox OSE (VB for short) is included with Kubuntu, and so long as I use the version that comes with 9.10 it will work for an Ubuntu 8.04 guest (the version of VirtualBox included with Kubuntu 8.04 lacks the PAE emulation, which an 8.04 guest requires).
Aaaaaanyway, having set up an Ubuntu 8.04 server "vanilla" machine, I've cloned it (well, used the VB GUI to export the appliance, then imported it as a new one). Everything works well, and VB even remembers to assign a new MAC address to the new machines, except... when the new machine boots, there's no eth0.
Turns out Debian (and its derivatives) use udev rules to map the MAC address of a network card to its device name. So my new machine boots (with a new MAC as supplied by VB) and the udev rules that would then automagically map the MAC address to the eth0 device no longer work, and... no eth0.
There's an easy solution for Debian etch, documented in about four-kazillion places on the internet, for example here. Sadly, the udev rule file that writes the rule (eh?) to map MAC to device is more primitive on Ubuntu 8.04, so that's not going to work.
Now for the good news: there's an even simpler way to achieve this, as documented here: simply delete /etc/udev/rules.d/70-persistent-net.rules and reboot. Problem solved!