I know it's a long shot, but I had a similar problem with my truck a few years ago. If I ran my heater on speed 1 or 2 everything was fine, when I ran it on high - my headlights and dash lights starting going nuts dimming out, coming back, etc. I diagnosed everything I could think of and couldn't find a problem.
It turned out to be my beautiful chrome plated Powermaster alternator. Apparently something internal was failing. During normal operations the engine and vehicle worked perfectly. I don't have many electrical accessories on my truck that draw many amps other than the starter, and I never have the lights on when starting the engine. I discoverd the alternator issues when I started having battery problems. I replaced the alternator with a plain ugly one and I haven't had a problem since. You may have a similar issue.
If not - I'd start by running a new fused power feed for the heater directly from the battery and a new ground wire to the frame or engine block. This should identify if there are too many amps being pulled through the circuit that is currently providing the juice to the heater.
