How can I prevent my outside heat pump coils from icing over?
Heat pump?

Keep salt away from the unit. Salt will attack and totally decompose the fins and will create electrolytic corrosion in the joints between aluminum and copper leading to destruction of the system. 

Icing during operation in a damp climate is normal, it's supposed to have a defrost cycle it runs through to remove the ice.

Heat Pump Operation: Heat pumps work on the standard phase change refrigeration cycle. In summer time for AC mode, the inside unit acts as the refrigerant evaporator and the external unit as the condenser. This is reversed in the cool season for heating, the external unit basically cools the outdoors in order to extract heat from the air and gives it up by condensing the refrigerant in the inside unit.

Heat Pump Defrost cycle: Since you're cooling already cool air that contains some water vapor, it's natural for frost to build up. In extremely damp climates, the fins can actually clog. To take care of this ice buildup, the heat pump system uses its shuttle valve to momentarily go into AC mode, shuts off the air circulation fan and extracts some heat from the house to be given up when the refrigerant condenses in the external units coils.

Operational failures that cause extreme icing: Older systems run this defrost cycle off a timer, newer ones have temperature sensors to determine frosting and the heating necessary to clear the coils. Failures in these can stop the defrost cycle from being run.

You can also have the shuttle valve relay fail or the shuttle valve freeze into the heat position which prevents the cycle reversal needed to do the defrost.

For Heat Pump systems that run as flooded evaporator type systems, low freon levels will cause extreme icing of the evaporator. This can cause the internal unit to become a solid block of ice during the AC season and for the external unit to do the same during heating season.

DIY Remedies: You've taken care of one major problem, keeping water from entering due to roof drain-off.

The unit must also be in a location that allows for water to drain away. Ponding allows for excessive water vapor in the atmosphere and is to be avoided. A drainage system that removes this would be a good idea.

So if you've taken care of drainage, it's probably time to have your local HVAC tech come out and give it a through inspection to figure out what's failed.