A game I bought has disappeared from my library, how can I retreive it?

I went into Steam to fix a problem, and it told me to go into the library and Right click on the game and click 'Delete' and so I did.

However, now the game is completely gone from my library, and the only way to get it back is to buy it again (even though I've already purchased it).

How can I fix this issue?

There are a few things that could be happening here:

1. You are viewing only your installed games

Ensure your library view is set to 'Games' to show all your games, not just Installed ones:

Set Library to All Games

2. Your credit card purchase was declined

Steam may allow you to play the game while it is in the process of authorizing your credit card.

In the event that your credit card purchase is declined, Steam will remove the games from the Library list. The next time you try to play the game, Steam will ask if you want to attempt the purchase again.
_{- Steam Support: Steam Is Asking Me To Purchase a Game I Already Paid For}

Please check your bank/credit account's transaction history.

3. Another Steam account purchased the game

If another Steam account was logged into your PC (such as a sibling or friend) and has installed games that you do not own, they will still show as 'Installed' in your library.

You will not be able to play them on your account, instead you will be prompted to purchase the game.
If you 'Delete' a game you do not own from within Steam, the (now uninstalled) game will no longer show up when viewing your installed games.

4. You installed/played the game on a 'Free Play' weekend.

The game will continue to show as 'Installed' but does not count as 'purchased'. After the Free Play weekend expires you will no longer be able to play without purchasing, but the game will still be installed.

When you uninstall the game it will be removed from your library.

5. Valve/Steam stuffed up

Take a screenshot of your library showing the absence of the game.
Find your receipt - check the email address your Steam account is associated to and save a copy of the purchase receipt
Contact Steam Support - Use this link, sign in to Steam and follow the prompts. Attach the screenshot of the missing game, and the purchase receipt. Provide them as much detail as possible.

6. You deleted a shortcut to a non-Steam game

You can add non Steam games (and also non-games) to Steam. Right-Clicking and clicking 'Delete Shortcut' will remove the link to the game/application in your library, but not uninstall it. If you re-add the shortcut to the game, you will be able to see it in your library again.

A continuation of Robotnik's answer...

7. You manually removed your license and forgot about it.

In order to allow people to transition from third-world countries (ie. Russia) and to first-world countries, Steam allows you to delete a license to a game to allow you to repurchase a license for it that does not have a region lock... Or that you really hated it (and know you can't get a refund)...

enter image description here

You can restore the license by going to the support page, navigating to the game that you've think you've removed; is missing... And if you did remove it, you'll see this in the It's not in my library menu: