I solved this a slightly different way: I found a very thin wallet (more of a flat coinpurse, really) and put my keys and a couple other cards in it. This makes it heavier (which helps) and sit cleanly in my back pocket; checking that it's there doesn't even need a pat. In theory, this increases the potential loss if I do lose my keys, but increasing the stakes also makes me check more often. (I'd found this previously when I bought a semi-expensive mechanical pencil instead of a box of new ones, and proceeded to keep track of it for longer than it had taken me to go through a box of 12.)

It also has other benefits: I keep my money in a separate, garden-variety wallet, but always keep at least $25 in the key-wallet for a bus ticket or short cab ride home, which is a nice hedge to have.