Mmmm!
If I interpolate your comments; fans do not run with lo speed relay in and hi speed relay out. Therefore I'd keep the hi relay out, lo in 'til you've solved problem. To ensure no problems keep an eye on temp guage, and minimze a/c use. (easy for me to say it's 33 F degrees here, coldest in 50 years).
I'm working with '97 Ford wiring diagrams and there could be differences with your '99. Operation as follows:
Operation should not be possible with ignition off as +ve feed to both fan relay coils comes from PCM relay which is fed from ignition relay. Inputs to PCM (temp and a/c) 'cause PCM to provide ground to hi or low fan relay coil. Fans derive +ve feed from fused battery connection via contact on fan relay. Therefore as suggested in earlier post, if fan relay contact is welded closed fan will operate.
One curious thing in Ford manual is that hi fan relay connector pin-out shows pin 1 as PCM and a/c switch, but this is not shown in circuit diagrams. A simple test would be; with engine off, release locking tabs and pull off the connector (c118) to this switch located at pass side engine compartment and see if fan stops.
Further troubleshooting to isolate problem will require multimeter, with one exception. If you feel able/willing to seperate hi relay cover from its base you could insert a small piece of paper between its contacts, re-assemble and insert in socket. If fans did not operate then problem would be in coil circuit. If fan continued to operate then fans are receiving +12 volts from somewhere they shouldn't be. Latter would be preferred fault to find.
p.s. Did you have any work done on car immediately before this problem appeared?
p.p.s. Sorry you went and bought new relay(s). I would have checked contact continuity first after removing from socket.
