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

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.