Here is an interesting idea that I had reading this. As a startup, what if you were to create a simple computer language that looked different from most other computer languages, at least somewhat different. Alternatively, just use one of the many really obscure programming languages out there, just make sure the applicant does not know it ahead of time. Give the applicant a 10-20 page reference manual for the language and ask them to make a simple program of some sort. Have them read the manual and write the program, hopefully while not looking over their shoulder, so they can relax. In the manual you give them omit one critical function or API reference, but make sure that info is available online (make it available if you made up the language). Then see what happens.

This would test programmers ability to learn a new language.