Frost heave requires 3 things:
1. Freezing temperatures, causing frost level to penetrate the ground
2. Frost-susceptible soil (generally means silty or clayey)
3. A source of subgrade moisture
The heaving is due to more than just freezing in the pore space, there is water migration and ice lenses are formed.
Typical approach used in traffic areas (including sidewalks)when there is frost susceptible soil in the subgrade is to replace the top several feet with non frost-susceptible (NFS) soil - usually a clean sandy gravel. Probably 24" minimum should be used. In very cold climate sometimes 6 feet of NFS material is used, or a combination of NFS material and subgrade insulation. Makes for expensive roads.
Your contractor should be aware of these standard techniques. While true a heaved area usually returns to original level (or almost) upon thawing, there is the inconvenience and possibly damage that occurs. If the excess water is due to Fall rain that penetrated the subgrade, the first winter could be worst, then it's not as bad in subsequent winters. It seems not to be the case for you.
A 'fix' may entail removing the sections causing the most trouble, such as at doorways, garage entry, etc., excavate 24", place 2" of subgrade insulation, backfill with NFS material, then repave or replace concrete.
By the way, this a very common occurrence, unfortunately, here in Anchorage, Alaska.
Regards,
Carl