Stainless steel, Inconel and titanium alloy fasteners are all prone to cold welding/galling. An anti-seize, such as silver plate or moly-disulfide, is usually applied to cres nuts. Cetyl alchohol or moly disulfide is used with titanium fasteners. I've also seen teflon/electroless nickel used on cres nuts that require lots of installation and removal cycles.
A common problem with deformed thread, self locking nuts is that the prevailing torque (ie. thread interference) tends to vary widely with the smaller thread sizes. The deformed thread locking feature is suppose to be within certain limits for running torque, but they never are. So I would check the running torque on a representative sample of the nuts you are using.
300 series austenitic cres alloys(with the exception of 303, which should never be used for a fastener) are the most prone to galling, likely due to their work hardening characteristics. Most high quality aerospace cres fasteners are heat-treatable alloys like A286 or 13-8ph, which are less prone to galling. One thing that also really seems to help prevent galling is to have a difference in hardness between the two mating parts.