HVAC maintenance should be scheduled at least once a year, ideally before the start of each season, to ensure optimal performance.