We were asking high level questions. At no point did we ask things like "have you ever used Microsoft Windows" or "have you ever used a desktop computer". It would seem we cannot take these questions for granted anymore.
The best strategy I've come up with is to build an intern program and source talent from that lower cost/risk pool. Pulling high level employees off the street was almost always a circus for us.