The lack of venting does cause the drains to flow slowly. In your case, mostlikely caused by the stack freezing again.
I would suggest you do one or a combination of the following:
1) Insulate the exterior portion of the vent stack. That way it is less likely to freeze during the coldest time of the year (one time fix)
2) Add a heating element around the ...