The client will only grab a new address from the keypool if you receive a payment on the address listed as "my address". It will then change the "my address" to a new address from the keypool.
Seems like the client could be more efficient by flagging addresses in the wallet as "unused" and simply using those before getting new address from keypool but likely you are right it is a small edge case.
This won't work. Just because an address never received coins, doesn't mean it's unused. I could have posted it somewhere. If the client picks this address when I expect a fresh address, I'll be using the same address for two purposes.