I'm not exactly sure, but I think I read somewhere that each time you kill a boss that has the potential to drop a key there is only a 5% chance for the key to drop. That makes them not necessarily rare, as keys are farmed quite a bit, but it does make it so that it takes a lot of boss kills to get a full set of keys.
I have a question about the Countess as well...
I play with two computers running D2. I discovered by accident that if I create the game with my second account (the parker) that has a character who has not completed the tower quest and kill the Countess with my first account, the chest in the final room pops. I figured that the addition of the popping chest would make for yet another chance for a rune or two along the way, and would add to the gambling funds that I rake in doing Countess runs, so I've started creating each Countess run game with my parker account.
However, I've yet to see a key drop since I've started making games with the parker (although I haven't done a whole lot of them that way so far). Just curious if anyone else does these kind of runs the same way, as I don't want to be eliminating my chances of a key dropping in exchange for the extra gold and extra chance at a rune or two from the chest popping.