You should also consider grouping your random hostnames under a dedicated subdomain. e.g. "xxx-xxx-xxx.users.tunnl.gg", that separates out cookies and suchlike.
I don’t have tunnl.gg usage numbers but I’m going to guess they are no where near the threshold — we were also rejected.