Are all blocks stored permanently on the Internet Computer?

They are not. The Internet Computer does not rely on historical blocks for verification purposes. Each replica only stores enough blocks to keep the network healthy (e.g., help other replicas catch up), and will delete old ones when they are no longer needed.

This is also due to the finalization algorithm. Once a block is finalized, new states can be computed deterministically, and only need to keep the latest canister state. Older blocks and older states are not that useful.