It takes 15-20 minutes to start the servers. I'll try to do some profiling and see where the hot pockets are. I know that a non-preloaded server takes more like one minute

This sounds like you have bigger problems. Neither of those delays (the 15 minute nor the 1 minute) is reasonable - as I said above they should be measurable in seconds on modern OS and hardware. If I were you I would increase the LogLevel in apache all the way up and see if that explains what the cause of the delay is. Otherwise, check the server for other problems: swapping could easily be one but also maybe bad disks or even a network misconfiguration as my anonymous brother suggested.

Good luck with your diagnosis.