Max is in most cases a mislabelled button: it should read A/C RECirculate, which is what it is on a lot of cars, and this position automatically calls for the A/C. Of course in winter, the A/C will not function because below 0°C, the pressure switch will detect low refrigerant pressure and cut the A/C...but indeed normally, this would not prevent the fan to work and the heat to be delivered.
But maybe the '95 model is different from my '93 and MAX is the top position for the fan speed...is it? IN this case, this is equivalent to the HIGH speed position and needs the High Speed relay to function normally...so may be this is the case here.
www.avigex.ca/xport/heaterrelay.jpg
By the way, using the RECIRculate position in winter will keep the moisture inside the car and cause the windshield and specially other window glasses to fog beyond control. HOwever, I use it sometimes for a short time to prevent outside snow to melt on a "not hot enough" heater core and fog the windshield: once the heater core is fully warmed up, the warm air will keep fog away and return to outside air intake is then acceptable.