This is equivalent to asking, "How good are virus scanners?"

Many crypto routines have identifiable constants but there are myriad ways to obfuscate code too so I'm not sure there's an answer other than: It depends on how hard they're trying to avoid you and how hard you're trying to find them.

The presence of AES instructions would be easy just from static analysis. Also loops of shifts and xors that are accumulating, etc. You could easily map the structure of various encryption algorithms into a static analysis tool. (I feel like the dynamic analysis proposed below about watching outputs being random is clever, but much more difficult).

> Also loops of shifts and xors that are accumulating, etc.

I think the problem is then to avoid punishing binaries for, e.g., using a hashmap :)

Statistically, any routine which results in randomized output from non-random input (and especially if it is repeatably deterministic) would be a good candidate.

Good symbolic analysis can identify simpler (e.g. RC4) encryption algorithms, but the run time is currently too expensive to run on every binary.

COM will use crypto routines as a matter of course - so practically every windows program will have these instructions.