What is the best way to evaluate the best candidates to get a new job (talking merely in terms of programming skills). In my company we had a lot of bad experiences with people that have good grades but do not have real programming skills. Their skills are merely like code monkeys, without the ability to analyze the problems and find solutions.

More things that I have to note: 

 - The education system in my country sucks--really sucks. The
 people that are good in this kind of job are good because they have talent for it
 or really try to learn on their own.

 - The university / graduate /post-grad degree doesn't means necessary that you know exactly how to do the things.

 - Certifications also means nothing here because the people in charge of the certification course also don't have skills (or are in low paying jobs).

We need really to get the good candidates that are flexible and don't have mechanical thinking (because these type of people by experience have a low performance).

We are in government institution and the people that are candidates doesn't necessary comes from outside, but we have the possibility to accept or not any candidates until find the correct one.

I hope I'm not sounding too aggressive in my question; and BTW i'm a programmer myself.