Esse tipo de situação é bem desagradável e mostra um dos grandes desafios a ser superados para o sucesso da arquitetura Bitcoin.
TL;DR Expirou e retornou o valor a minha carteira, acabo de ver.
Obrigado pela ajuda Adriano.
O procedimento mais simples nesses casos: você precisa criar um novo address na sua carteira
blockchain.info e enviar todo o seu saldo para esse address (pagando fee), e só fazer nova transação quando já tiver algumas confirmações desta.
E a versão longa com o motivo do procedimento:Quando o usuário emite uma transação válida, mas sem adicionar fee, esta poderá ser confirmada a qualquer momento, mas ninguém sabe quando será, podendo ser daqui a uma semana, podendo ser daqui segundos, é completamente indefinido, e inclusive poderá jamais se confirmar, embora isso seja muito improvável.
Aparentemente a unica consequência para a carteira
blockchain.info é sumir a transação depois de 3 dias, deixando de exibi-la (nunca vi essa regra escrita em nenhum lugar, mas é o que acontece).
Nessa carteira o saldo voltará a aparecer como se a transação nunca tivesse sido emitida, no entanto essa transação ainda poderá ser confirmada (pois ela ainda está sendo propagada pela rede), o que fará ela voltar a aparecer na carteira como gasto.
Vejam esse relato (encontrado aleatoriamente no google) que demonstra isso:
http://bitcoin.stackexchange.com/questions/9709/do-unconfirmed-transactions-expireI recently sent 0.03 BTC to [...] without a tx fee from a blockchain.info wallet.
It stayed for about 3 days without being confirmed and it finally expired.
[...]
After it expired the sum of the transaction was added back to my balance.
Any details of the transaction disappeared from my wallet and from the block explorer...
Several hours after the expiry a new transaction has been issued automatically with the same amount to the same [...] address.
* a transação expirou e sumiu, depois apareceu novamente 
- possivelmente confirmada.Isso é o que acontece na
blockchain.info, mas a carteira Bitcoin-core (Bitcoin-QT) funciona diferente e irá continuar propagando essa transação indefinidamente até que seja confirmada.
Para usuários da carteira
blockchain.info a unica forma simples de garantir que a transação "expirada" jamais venha a se confirmar, podendo assim reenviar o valor sem medo, será forçar uma
double spend transferindo todo o saldo da carteira para um address novo (da própria carteira), dessa vez pagando a fee.
Após algumas confirmações da nova transação a tentativa anterior se tornará uma "transação inválida" e portanto desaparecerá em definitivo de toda a rede.
O problema é que esse procedimento só poderá ser realizado após os 3 dias, pois antes disso o próprio
blockchain.info irá impedi-lo de forçar uma double-spend.
Para realizar um "double spend" antes dos três dias, ou quando a transação foi realizada no bitcoin-core, será necessário exportar as chaves privadas da carteira e importá-las em uma carteira nova, para então enviar uma nova transação para um novo address da própria carteira (bitcoin-core, pois na
blockchain.info não dará certo).
Esse assunto é tenso, só vai entender quem já está no Bitcoin a algum tempo.
