Old Smokey, some truth in the story. The long held theory is that in OATs of -40 C or colder there is insufficient free water to be an icing problem, all of the water would be ice crystals. What few ice crystals there were would indeed bump off the aircraft surfaces, thus de/anti icing was not required. Depending on the type of de/anti icing system, it could be possible to melt some crystals and get ice particles to stick on the surface with de/anti icing selected on in these conditions.
However, more recently, some aircraft have reported airframe icing in very low temperatures and rarely some engines and ice detection systems have suffered difficulties; ice crystals blocking tubes / overcome heating systems. The engine problems were associated with Cb anvils where there was a mix of water and ice crystals, the water became the glue for sticking crystals together. The particular manufacturer changed the definition of icing to include very low temperatures in the AFM and modified the engines.