Eventually we took the one with the outdoors obsession to the vet who told us we could either put her on Prozac or start letting her out. At that point we started letting her out (in our quiet suburb nowhere near a major road), and she instantly became an extremely happy cat. Her sister lived as a happy indoor cat, while she would go out during the day and come in at night. She came back every night and they both lived to pass of kidney disease when they were 15.
I know a lot of people are extremely against cats going outside, but compared to some of my college friends who kept "emotional support" cats in minuscule dorm rooms, I would much rather let a cat out than imprison it. I don't really buy the songbird thing in built up suburbia.