Where is the public key corresponding to my address stored?
Yes, a transaction includes the public key. So, only when you spend the coins from an address a public key actually becomes public (unless you have shared it with anyone otherwise).

So, as long as you don't reuse addresses, the public key is only known after a transaction, which usually is just a few confirmations away from the address' balance to be 0.