Chiming in from the Canadian prairies where, yes, heating underground parking garages is normal practice - lots of frozen and burst pipes otherwise, not to mention frozen car engines and tenants ranting at your heels :B
Wufi, the most common heating practice I've seen out here has been the unit heater (usually Trane :B ) Being in gas country, natural gas is the normal fuel; not sure what area you're in, so I'm not sure what your normal fuel is, but unit heaters are available in oil- or gas-fired models. I second the suggestion of talking to Engineered Air; they are very good and know our climate variations inside and out.
In addition to unit heaters, I have also seen finned-coil heat exchangers used. These are less common out here because of problems with freeze-up. Here in Alberta, it is not uncommon to get cold snaps where temperature can drop to -30C or even -40C. Water in a finned-coil exchanger can freeze at these temperatures, as it loses its heat so quickly, so a glycol mixture is usually used in the lines, 50-50 being the norm. You will want to keep that in mind if you are still considering a water-filled finned-coil exchanger for your make-up air unit.
Hope this helps
-==- GeneratorGrrl
"Eat well, exercise regularly, die anyways."