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):


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