My own surprise was mostly to do with highly paid individuals with a great track record on paper, but who seemed to be barely able to solve basic problems (to the level of making me wonder whether they had actually written a single line of code in the past few years).
Regarding CS majors, there's always the possibility of an individual being great at the theory part, but not having much programming experience. This should be rare though; during my own CS degree, we coded so much that I was frequently dreaming about code. If it's provided in the CV, I like to scan through the subjects list of the candidate - the ones who don't actually like programming seem to have an aversion to taking CS courses for elective subjects. As always though, YMMV, and it's a good idea to keep an open mind.
why does it amaze you? my experience of 'self taught' individuals in the general case is that they have a rich understanding of the subject by necessity.
conversely my experience of education is that it trains you to solve education style problems - which are essentially absent from the real world - where being able to invent and implement a slightly broken solution in an hour with 30 seconds notice is much more valuable than being able to solve a problem you know about far in advance and are given loads of information and guidance to help in preparation for it.
on the other hand if i wanted someone to do research then a CS major might be a better choice. :)
