Then I've sent a new transaction to a different address but with a higher fee (dynamically calculated), the transaction appears on my bitcoin-qt client, but if I search for its transaction id on blockchain explorers, e.g. blockchain.info, it says that this transaction doesn't exists.
I saw a similar case yesterday. After several hours, the new transaction confirmed and the old transaction disappeared from block explorers. I expected this to take longer.