I used to cut keys in a previous life and ran into this situation quite a bit. You're right, the machine at HD is idiot-proof, but it's also skill-proof. Before you go to the dealer for a VIN key (which likely won't work any better than your last copy), just go to a small hardware store with an older, non-automated key machine. Ask for their best "key guy" and explain that the lock cylinder and tumblers are worn. There are a couple ways the blank key can be aligned with the original in the machine, and often you can't just "bottom out" the old one against the shoulder stop, since the old one is worn. It works better to align the tips of the keys instead... Like I said, it takes a little experience. He or she should be able to cut the key and then use the wire wheel to wear down the new one to match the wear on the original key. It takes some time and skill by the key cutter, but I've been able to "age" lots of new keys and get them to work when a sharp-cut key wouldn't even go into the cylinder. Good luck!