Rust is statically typed, so information about all types is known at compile time.

That's not exactly true. Lifetimes are types and sometimes each iteration of a loop has its own lifetime-type. This means it's not always possible to number lifetimes while compiling, because that would require predicting what the program does while executing.

Rust is statically typed enough that it proves things about types while compiling and can "erase" type information. But it's quite common to compile a program that has countably infinite types.

This just means that borrow-checking loops and recursion involves induction - it's not terribly exotic. But that's why Any only works for 'static values. Once borrowing is involved it will run out of numbers.