The package menu shows all known versions of a package.
As such, you may see an installed package listed as available as well, for
instance, if there is a newer version of the same package available, or if the
same package is available from different archives.
To delete such a package, simply scroll down in the list, or use C-s <PACKAGE-NAME> to search for occurrences of the package. Once you find the installed version of the package, press D to mark the package for deletion; if this fails, press d. You should see a D mark in the left before the package name. Press x to execute the action and actually delete the package.