That's an interesting point. I interpret the prize's criteria "for contributions of a technical nature made to the computing community" to be less in Claude's space and more in the applied space. Scrolling down through the list of past winners, I've implemented several of the work of winners and am using the WWW right now to communicate this.
On the other hand, I think I use Claude's work in the same sense that I use Kirchhoff's laws everyday.
Stephen Cook, Micali, Goldwasser, Rabin, Scott, Karp, Hartmanis, Stearns, Manuel Blum, Yao and Valiant. These are all pure theoreticians; I didn't include data structures people and applied-ish cryptographers like RSA and DH.
More than a significant fraction of Turing awards have been won by theoreticians.
I see a number of theory guys on the list. That's the thing that's interesting about Shannon's exclusion: for any given explanation, there's a counterexample on the list. I've never really known anyone involved very seriously in the ACM, those guys probably know why he was excluded.
On the other hand, I think I use Claude's work in the same sense that I use Kirchhoff's laws everyday.