Is there a database of all transactions? The blockchain is a database of all valid transactions, but is there a company/project that also logs all transactions which were broadcasted, but didn't made it to the chain? Blockchain.info for example, keeps a history of all double-spends, so I assume they keep such a log, but its not publicly available.

I could very easily calculate how much was lost by transaction maleability if something like that was publicly available.
I haven't seen anything that is tracking all transaction including failed ones, etc although  this project looks like it has promise:

http://codesuppository.blogspot.co.uk/2013/07/work-in-progress-on-bitcoin-blockchain.html

That said I'm not even certain what your suggesting would be possible.  Consider the following scenario.

If a person / organisation were monitoring and recording all transactions and I were to submit a transaction that then where then to be marked invalid and discarded, the nature of bitcoin is that you send your transaction to peer nodes who in turn will broadcast those out if they verify the transaction.  Now If someone can explain to me otherwise than fine but surely this transaction would only have a limited number of broadcasts before a different chain showing it to be be invalid was received and the erroneous block discarded.  Now unless the 'monitoring party' where within the peers that received the broadcast there would be no way for them to track it?