Faulty heaters valves become a fact of life sooner or later.
The valves should remain fully open (max heat) when no power is applied.
First of all check the voltage supplying both heater valve coils with the motor on and the heater set to fully cold. You should measure 12 volts.
When turning the heater to full hot, you then should measure zero volts.
That will at least confirm the problem lies with the heater valves themselves.
What causes them to stick is are internal rubber seals designed to keep water out of the solenoid coil mechanism. These seals eventually disintegrate and as the water gets into the solenoids sludge and corrosion develops causing them to jam.
They can jam in any position hot or cold. If you give the top of the valves several sharp taps with the handle end of a hammer they may free up and function normally again for a while. Mine did but in the end I still had some heated air coming from the passenger side vents and as it's summer here now I decided to replace the valve assembly which has fixed the problem.
Shogun had some good pics a while back of a disassembled heater valve.
Shoguns thread is here...
http://www.bimmer.info/forum/showthread.php?t=16409
The seals that go bad are shown clearly in this picture...
Er...sorry about the free ad for the other forum...
You may still have other issues but if the heater is hot when it's turned off, or cold when it's turned on, provided the measured voltages are correct, then you have a faulty heater valve.