Nah, that's not it.

I forgot to mention that I can't see the transaction on my receiving wallet/address/computer at all, not even as 0/unconfirmed. I hope that's a good sign.
Anyhow I'm rescanning the blockchain right now, will update here on any progress or failure.

About a week ago, I had a no-fee confirmation take approximately 12 hours.

You can't have lost the bitcoins. If the transaction never gets committed, the 80 BTC never left. Your client just thinks they did. If the transaction does get committed, the 80 BTC will arrive at their destination.

Worst case, you can do the following:

1) Note the transaction ID.
2) Stop the client that sent the transaction.
3) Make sure the transaction is not in the block chain.
4) Make sure the transaction is not in the list of pending transactions. (Available here: http://bitcoincharts.com/bitcoin/ )
5) On the client you stopped, make a backup of the 'wallet.dat' file. Put it in one or more safe places.
6) db_dump the wallet.dat file to a text file.
7) Remove the wallet.dat file.
8 ) Search the text file for the *reversed* transaction ID. So if the txid start 1234567890..., search for 9078563412.
9) Remove the line starting with 02 and the following line, such that those two lines contain the transaction.
10) db_load the text file into the wallet.dat file.
11) Restart the client passing it the '-rescan' flag. The transaction should be gone.
12) Double-check the transaction is not in the block chain or list of pending transactions. If it is, stop your client and revert to the saved 'wallet.dat' file.

You're done. You're now in sync.

In the future, leave transaction fees at their defaults.

Alternatively, if you're in no hurry, just wait many hours with the client running. The coins will age and the transaction will gradually gain priority.

(The client really needs a way to delete an unconfirmed transaction.)

Had the same thing happen to me. For some reason the sending client did not transmit the transaction to the network.

A developer in IRC told me that it'll try again every few days (yes, days).

What helped me was restarting the sending client every 5 minutes for 2 hours :-)
Then the transaction appeared on the receiving client.

oh lol my bad dude, definitely update that!

It should be noted that you can never actually lose funds this way, only have them trapped by the wallet, a little bit of effort on the part of someone who knows what they're doing and the funds would be available again.

I had the same problem once (on OSX client, which is buggy). What I think happened was that my block chain got somehow corrupted - or even my wallet.dat. Do you have an earlier backup of the wallet.dat?

How I fixed the issue:

1) shut down bitcoin client daemon
2) take a backup of your current wallet.dat (you could backup the block chain DBs as well, for later debug or what not)
3) delete the current wallet.dat and all block chain data (usually in the same folder)
4) replace only the wallet.dat to the folder (I used an older backup, I'd recommend that since I suspected that the stale transaction was already written to it. You could try the current wallet.dat as well if you don't have backups).
5) restart bitcoin and redownload the block chain (on OSX this can be _really_ slow. I mounted a RamFS for this purpose.)
6) Once the block chain is up to date, you should have a balance that includes the 80 BTC you thought you lost.

Let me know how it goes or if you have any questions.

Could you please update the title to say that it was solved? All these threads of losing bitcoins are not good for the image of bitcoin. Thank you !

You don't have to update your wallet.dat right? because it will automatically update on the network once it downloads all the blocks? correct?

I think the client needs to have a separate file for private keys and transaction data, if the wallet file does contain transaction data. a consolidate button would be nice too. that way, once or twice a month we could do that and have the coins in 1 neat and tidy address, so overall we would use less space in the blocks. sometimes i look in the explorer and see like 10 addresses give me like 1BC combined,kind of wasteful.