Water coming into post hole for deck

It is a little odd that only a few of your holes filled in with water, it may indicate something underground like a spring. More serious conditions would include hitting a sewer or irrigation line but it should be pretty easy to determine if this was the case.

Typical deck footer construction in freezing locations calls for full-depth concrete footings poured using sonotubes (cardboard form tubes) all the way to a few inches above the surface. Posts are anchored to that concrete but shouldn't be buried in it (building codes may vary).

This article explains frost heave and how to counter it. For large deck installations in especially frost-prone areas, they use concrete "bell" footings that are wide at the bottom, these help resist frost heave and upward movement. But as long as your footing is deeper than the frost line, it shouldn't be affected by the heave as it's nestled in deeper soil.

According to decks.com water in the hole is not a problem for mixing concrete. You may want to compact gravel around the concrete form tube before or after you finish it.

Finally, this article suggests putting large stones into the wet spots at the bottom so the mud flows into it and provides a good base for the concrete footing. You wouldn't want the stone layer tall enough that it puts your concrete footing above the 42" frost line though.

This is not uncommon as in some places the water table is very close to the surface. I used to live at a place in Ohio where if you dug a 1' hole it would fill with about 10" of water.

The consideration here is not freezing since you are below the frost line but to ensure that any materials you put down the hole can stand up to continuous water exposure. That pretty much rules out any wood-based product as they will deteriorate due to water exposure.

I'd probably opt for a concrete post extending well above the current water line as it may rise and fall with rain or other weather.