Default [Q] Very slow mobile network search and registration

This is on a rooted I9505 with a custom AOSP ROM (C-ROM).

KNOX is 0x1

Baseband version: I9505XXUFNA1

Mobile carriers are 3 (Three/Drei) in Austria and T-Mobile in the US.

Network search after cold boot takes up to 5 minutes before it shows the available carriers and registration takes up to 2 minutes after selecting correct carrier. This is really annoying, especially after briefly losing network connection in the subway or an elevator.

It used to be a lot faster, but the phone needed to be carrier reset after bricking the EFI partition and clean installed with a Samsung ROM. Is this modem related or what else can you suggest to troubleshoot the situation and get back to normal?