How can a pitot tube freeze when it's heated?
Captain Bill Palmer, in his book "Understanding Air France 447" has a section dedicated to answering that very question as it pertains to AF447. Although there is no way to know for certain he puts forward some possibilities.

He quotes a commenter on a website: 


  One commenter on the Weather Graphics website’s AF447 article provided this interesting observation: “I'm an aircraft icing specialist and wanted to point out a factor that hasn't been discussed much … high ice crystal concentrations. I've seen flight test data from power rollbacks due to flight in high ice crystal environments … In our case, the crystals collected within heated, aspirated Ram Air Temperature sensors, forming a 0 ° C slush…”


He notes that just before the pilot tubes clogged, the sound of ice crystals hitting the windshield could be heard on the CVR.


  Ice crystals bounce off the exterior of an airplane and cause no visible ice accretion, but they can enter the probe inlets. When highly specific climatic conditions exist in combination with certain combinations of altitude, temperature, and Mach, the concentration of ice crystals entering a probe can exceed its capacity to melt and evacuate the moisture through its drain holes. The result is that the ice crystals form a physical barrier within the probe that disrupts the measurement of total pressure.


The particular type of ice that may have been responsible was a substance called graupel.


  Graupel forms when tiny supercooled water droplets adhere to snow crystals to the point that they engulf the snow crystal itself.



Graupel. Photo from Wikimedia commons

Capt. Palmer notes factors that make graupel a possible suspect:


  
  No airframe icing. The supercooled water theory is discounted by the fact that the A330's icing detectors were not triggered. 
  Graupel has large enough particles to be audible on the voice recorder. It takes a particle with enough mass and inertia (a given density) to hit the fuselage with a sound, instead of flowing around it with the relative wind, like snow. 
  Graupel has enough mass to temporarily overwhelm pitot anti-icing when concentrations are high enough. The pitot tubes are hot. But even if you put a snowball on a hot skillet it does not melt instantaneously. If there is enough mass in the blockage, and in combination with new particles being added to the blockage as the first ones melt, it may exceed the pitot tubes capability to melt the obstruction as fast as it is introduced. Graupel is of significantly higher density than snow. 
  Graupel has sufficient blocking properties to prevent efficient transmission of dynamic pressure within the pitot tube.For example, water can flow and transmit pressure within the pitot tube, though it too can alter pitot-static readings, a physical non-fluid blockage could shield the pressure sensing port. 
  The likely presence of snow or similar form, as evidenced by the St. Elmo's fire discussed by the crew. The accident report stated that the sound of ice crystals hitting the aircraft can be heard about 20 seconds before the airspeed loss and autopilot disconnect.
  


It must be noted that the exact cause of icing problems on the A330 was never completely identified but it was specific to the particular brand of pitot tubes originally installed. Airbus was in the process of replacing them all with pilot tubes from a different manufacturer.