Deleted icons reappear on dock after reboot

Maybe try both resetting and restarting the Dock.

(I know you've already reset it, but I'll provide full steps below for the benefit of others):

  1. Go to Finder
  2. Press and hold the option key down
  3. Now go to the Go menu
  4. Select the Library option to open the User's Library folder. You can let go of the option key now.
  5. Go to the Preferences folder (i.e. within the Library folder)
  6. Find and move the com.apple.dock.plist file to the Trash
  7. Now open Terminal (usually located in Applications > Utilities)
  8. Enter this command killall -KILL Dock
  9. Press enter
  10. Re-add any non-default icons (i.e. apps) that you've added to the Dock, and remove any you don't want.