Is blockchain.info storing paper wallet (offline) private keys? Does anyone know if it is safe to use blockchain.info "Watch Only" addresses?
The real question is what happens after I perform a transaction - sending BTCs out of such a wallet. Will blockchain.info record the "offline" private key used for such transaction somewhere on the server?
My Wallet's warning for watch-only addresses ("You will not be able to send bitcoins from this address without later providing the private key") can be a bit confusing.

It's possible to specify an address and watch it. And it's possible to import a private key to be able to use the associated address as if it was generated with the My Wallet client.

But these two features are really unrelated. You don't "send out of a watch-only address", rather you import a private key thus making it no longer a watch-only address.

So the question is really whether My Wallet's "Import Private key" feature is safe. I don't have the official answer, but I see no reason why it shouldn't follow the same policy as other keys - the private key is encrypted in your browser (and as needed, decrypted and used to sign) and never leaves your computer in plaintext. If that's true, it is safe as the server never sees your plaintext key.