Currently many distributions create a MAC address to ethX mapping during installation. This ensures eth3 remains the same interface after every reboot.
Why not implement that same approach using PCI slots instead of MAC address?
So instead of associating a MAC address with an eth device, associate a PCI slot with each eth device.
That way we'd still have the ethX names we like, order is fixed (after first boot) and we can determine which eth interface corresponds with which physical interface. If the order is important to the user (eth1 must be pci1#2 on every node) then modify the configuration during install.
I really don't like the # in the new names by the way. It will cause a lot of problems.