Once ice is off there should be no problems finding oxygen as long as there is surface wind hitting your pond. You are not running it very long (25 minutes) and in 4' of water they should be able to find other warm water in the depths so that seems to rule out 'supercooling'

What type of fish are beaching or gasping? Small, large? all the same size class or mixed classes?

I'm wondering if you have a source of sulfide gas or methane gas being released making them suffer from the toxin effect rather than lack of oxygen? That might explain the last winter kill as well if it occurred around the same time of year?