A few years ago I purchased some bitcoins from MtGox and decided to retrieve them to the wallet on my PC.
Now without getting into detail I got sick of the headaches and ended up uninstalling the program before I received ANY coins. In retrospect I could not have been a bigger idiot.
Now these coins are worth a small fortune and I've done everything I could think of to retrieve them. I contacted MtGox and all they could say was that the network says the transaction shows as complete. I have extensively and on a byte level searched the PC in question for remnants of my private key, with no success.
Which brings me to the question at hand.
I still have my public key, the knowledge the coins were never received and access to the MtGox account they were sent from.
What can I do? MtGox simply left it at "the network says it was completed, therefore fuck off"
First step: stop using that harddisk absolutely immediately. Either get a new one and start using that or make a complete image on the byte level (for example with dd in linux). Any write action you do on your current disk may overwrite your private key (assuming it hasn't already).
For further steps you need to provide more info.
Which bitcoin wallet were you using?
Was your wallet encrypted with a password, do you remember?