How are the connections themselves? Sounds like that could be a possible culprit with intermittent operation...but that wouldn't explain the lights working when you replaced the fog light relay. I'm trying to think of all the possibilities.
my advice would be to try replacing the fog light relay again...and then if that doesn't work...replace the headlight relay...and if that works, then splice in the new relay like your mechanic suggested.