exp(M) (shoul've been exp(t)) is the growth of Internet.
Any sane policy will have to account for it (and, no, just
doing three levels is not enough, there should be a way
to go into more levels if needed later).
The idea of using "randomizing" sub-domain is to get people used
to the idea of randomization in domain names. Then it can be
moved into protocol or implementations. It also fixes the name
collision and transparent introduction of multiple registries.
There is no other way to satisfy N users when every one of
them wants to be named "Itty Bitty Machines".
--vadim