If sudo apt-get remove --purge deluge succeeded, then the deluge package was successfully removed.
If menu items still appear in your dash, it doesn't necessarily mean that the program is still installed, just that links to it remain somewhere. Possibly, the dash keeps its own cache of what is in your menu, and it takes a little while to realise that a change has been made.
Feel free to go ahead and reinstall deluge now to see if it works.
For future reference, you should look for dotfiles in ~/ or in ~/config that relate to Deluge. That is the most likely place it would store data for your account. Try purging or renaming that instead. That may solve your original problem with it (rather than re-installing it).