I think it needs to store device names because deterministic breaks potentially if you add a new device which is detected earlier in the boot sequence and renames old device.
My opinion is that it should probe for existing devices and if they exist give them the same name as previous boot and then look for new devices.
That seems like a reasonable strategy, although it's not quite perfect for devices that are likely to get added/removed a lot. But they are likely to be USB devices and users can add static mappings themselves in most cases. Which kernel/udev versions were you using that exhibited this behaviour? Also, what sort of machines are you using them in? Granted, nondeterministic behaviour can't be guaranteed to work everwhere, but I have a large number of systems with multiple network cards and so on that doesn't show this behaviour at all. Most of them are running fairly recent kernels (2.6.15+?) and udev, and I've not come across this. Basically, if there's a particular kernel/udev version combination I should avoid putting on my multi-nic firewalls, that would be good to know.