first CiviCRM request of each session takes 4 minutes, afterwards works fine
I had a lot of trouble tracking down a problem that sounds the same. We ARE behind a firewall so pingbacks to CiviCRM etc WILL timeout. The last piece of the puzzle (once normal version checks were disabled) was adding this to civicrm.settings.php

global $civicrm_setting;
  $civicrm_setting['CiviCRM Preferences']['communityMessagesUrl'] = FALSE;