The bees will know that they are queenless almost immediately.
If you are pulling a queen that's laying well off of of comb from another hive or a mating nuc you can introduce her directly and have no problem 90% of the time, even if they've only been queenless an hour.
If she's in a cage, it also can go in directly, but a candy release to allow her pheromones to spread throughout the hive.
In a few days the bees will have eaten through the candy and she will be out and accepted.
Either way, if your queen is killed by the bees, the most likely cause is that there was already a queen present in the hive -- often a virgin.
(Sometimes a daughter queen and her mother will both be in the hive at the same time, laying, and not fight...so just because you kill one queen doesn't guarntee your hive is queenless.