The most generally effective trap I have found is glue traps. They are an awful device but very effective. Unfortunately, you have to kill the trapped mice yourself. They have usually sustained serious injuries in an attempt to free themselves, so even if you wanted to free them, it's too late. They will also catch other pests (like insects), while being relatively safe for any larger animal - I wouldn't put one anywhere a cat, dog, or child could get into it, but if they did, liberal application of a solvent like rubbing alcohol will solve the problem.
One time that did not work either, and after seeing an HN post on the matter, I filled a pyrex mixing bowl with cooking oil. It turns out this is fairly effective too. The video posted showed that dozens of mice had climbed in - I only had one left, but it worked. They get in and they can't get out. If you want a nonlethal trap for some reason, this is a good choice, and it's easy to put together if you don't have time to run to the store for a glue or snap trap. Of course, if you would like it to be lethal, well, you have the same problem you have with glue traps: it's up to you to deliver a coup de grace.
I have actually wondered why people go with poison - as the article even mentions one of the reviewers complaining about, you end up with rotting mice/rats in inaccessible places.