air will bleed out as you bleed the cooling system. if the radiators full when ya pull the cap its a bit less likely (esp if you dont hear the gurgling/babling brook sounds with the blower fan on low and reving the engine)
start the engine and as it warms up to operating temp (blower fan on high at this point) monitor the heater core hoses for temp increase, one will be hotter than the other, if both hoses are pretty damn close to the same temp as it gets hot its likely the airflow issue is in the hvac box/flap doors preventing the air from going over the heater core.
if one hose is way cooler than the other its restricted flow through the core and its just not enough volume of hot water to heat the air.
with your heat working better at wot (more or less meaning high wp speeds) my guess is dex is clogging the core.
easiest fix is to determine the hot/cold sides remove core hoses from engine (leave coolant in the core as much as possible, take "hot" hose and direct it towards catch pan, stick air nozzle into the "cold" side hose (aka core outlet/return to engine) plug partially with a thumb and blow through it.
this should backflush most if not all the debris/sludge through the core, dont use too much pressure to blow the core out Use yer thumb to bleed too much pressure. repeat with clean water till you dont blow chunks...
on the other side of the coin if youve replaced the wp with a valuecrap or eqiv i've had 2 in the last year loose fins from, or self mutilated their impellers, and what your describing is also possible with a bad wp impeller.
good luck, James