Since the registry is a database, I would expect adding and removing branches and leaves would create fragmentation that, in the age of spinning metal and memory pressure, could create performance issues. A file system is easily defragmenters with tools available in the operating system itself, but not the registry. I’m not even sure how much of it can be optimised (by doing garbage collection and defragmenting the underlying files) with the computer running.
If it makes use of indexes, changes will lead to the indexes themselves being fragmented, making performance even worse.
The registry was capable of being compacted, negating the need to defragment it. This was done via the standard Windows Backup utility provided OOTB.
As for performance, the registry was mapped in paged pool memory[0]; only sections in-use needed to be mapped. Other hives were volatile and never persisted to disk. When data is added to the registry, the paged pool expands to accommodate. Maximum registry size is based off of installed memory, up to a limit.
Registry subkeys are organized alphabetically in an internal list; searches are binary searches rather than using an index. Searches begin in the middle of the list and go up or down based upon the alphabetical value being searched for (so start at 50% -> up/down, split remaining list 50%, up/down -> repeat until found).
You can find more info in Chapter 4 of Windows Internals 4th Edition.
Needless to say, none of the concerns you presented were valid back in the dark days.
If it makes use of indexes, changes will lead to the indexes themselves being fragmented, making performance even worse.