We ended up going for a three-stage process.
1, we sent them out a basic test. Originally, this was a 3-page address book (add, list, search). We eventually decided this involved too much boilerplate and switched it to a choice of a couple of programming contest questions. Much less boilerplate, more fun, faster and interesting to see how they approach the problem.
This was a interesting filter - it proved they could write basic code, but also provided a check for their CV. If they said they were passionate about TDD, for example, they'd better have provided tests with their solution.
2, we had a technical phone interview. We split this into three parts - they tell us about themselves, we ask technical questions, then we tell them about us. About 30 minutes all up. We ended up with a set of question from which we'd choose a subset ... examples include 'what's polymorphism', 'what excites you about software dev at present' and the perennial favourite - 'design a OO chicken'. We did have someone design a chicken that subclasses Carnivore, a terrifying prospect.
3, if we liked them and they liked us, we got them onsite. This was the point we asked the more in-depth questions, and tried to get a feel for them personally. We also planned to implement a pair-programming exercise at this point, but we were stuck with a hiring freeze before having a chance to try it out.
We did, however, get all the bits together to do it. And what we ended up with was a simple task - import an existing CSV file into an existing DB. We planned to offer them the internet, the DB connection details, the CSV file and Eclipse, and work with them to see how they approached the problem. It's relatively simple, but it offers a lot as to whether they code from scratch, look for libraries or find something even crazier to fill the gaps.
It all gave us pretty good results, although it filtered out a lot of people. No doubt, we missed some good people. But I'm pretty sure we also managed to skip a lot of rubbish candidates as well.