That's an odd symptom all right. Have you experimented to see if cycling the ignition switch makes a difference? In other words, does it always take the same time before starting? Assuming it's consistent, the first thing I'd do is put a test light or voltmeter on the relay socket to determine whether or not it's getting the signal in the first place. Terminal 86 should be at +12 volts with ignition on. If the PCM (engine computer) is getting its signal out, terminal 85 should be at ground potential. So if 86 is 12 volts to the chassis, but not to terminal 85, you know the problem is in the PCM or between it and the relay. If terminal 86 is not at 12 volts, look for a wiring fault. If there is a good 12 volts between terminals 85 and 86, then the correct voltage is reaching the relay. Terminal 85 shares a line with terminal 85 of the automatic shutdown relay, running to terminal 51 on the PCM. Terminal 86 taps into a common positive line that feeds many other components, all fed through the ignition switch.
The switch portion of the relay is between terminal 30 and 87. 30 should show +12v with the relay removed, and the relay should switch +12v to terminal 30, which is the supply to the fuel pump. The fuel pump is grounded at the tank end. If the relay is getting its juice, try another relay, or start tracing back toward the pump. If you bridge between 30 and 87 the fuel pump should start right up.
Some people (including me) have had problems with bad splices in the wiring harness causing voltage drops and other odd symptoms, so it's worthwhile to go through the pertinent wiring carefully with an ohmmeter if voltages aren't up to par.
Pin 87A on the relay is not used, by the way.
Looking at the schematic I notice that the fuel pump relay seems also to supply the positive voltage to the heater on the oxygen sensor, and I wonder if some problem with the sensor heater or its wiring might foul up fuel pump operation.
Good luck!