[lgunsch]

The OS must search page tables to allocate them to a processes memory space upon request. Without fixed sized pages the OS has to search for appropriately sized areas to satisfy allocation requests. Fixed sized pages solves this problem.

Edit: you would also then suffer memory fragmentation, not just lookup latency.

For already mapped pages latency would be an issue as you described.