"The vessel you are trying to create already exists" note will be displayed every time an user tries to create a vessel in Modules > Master Data > Vessel Administration > Create new - using a vessel name which is already in use.
After checking if that vessel exists under the Active vessels tab, the user can check under the Deleted tab where the vessel is most likely to be found.
To get that vessel back under Active and be able to use it in Vms just press Undelete, that vessel will then, without warning, be moved back to Active. A delete permanenttly option is available as well, but deleting a vessel to which historical voyages are linked will cause historical reports to fail.