I have a debian dedicated server, when I login via SSH it's just saying:

-bash: fork: Cannot allocate memory

If I try any command, e.g. 'ls', it says that message. I had a similar problem before which was solved by killing the process that was using up all the resources. But this time I can't get a process list using 'top' because I just get the above message.

If I could get a process list then I think the 'kill -9' command would work because if I try this command with a random process ID it says process not found for that ID, this could be the only command that works?

I've tried to reboot the server from the webhost control panel, although the CP said it was successfull I don't think it has actually rebooted.

Edit: Also... the websites hosted on the server are all fully operational as if there is no problem at all.

Any help is appreciated!

Try booting from the install media, recovery/rescue mode eg
linux rescue
mount the hard disk and check the contents of /var/log. You've either got a runaway program (likely), or a very popular website (not likely).
Could well be someone cracked one of your websites and its spamming or rootkitted.
The contents of /var/log should clue you in. If not, look at running chkrootkit www.chkrootkit.org or rkhunter http://linux.die.net/man/8/rkhunter

Thanks for the help Chris.

I logged onto the Plesk control panel running on the server and was able to kill the process that was using up all the resources.

SSH is working as normal now.

Good
However, make sure you find out the root cause, or it'll happen again...