ЯR, спасибо что разъяснили, я боялся что если у меня не меняется иконка то и у других она будет отображается не такая.
Если кому будет нужно то по совету - 

либо производить очистку кэша иконок Проводника с его перезапуском.

Я создал файл .bat для очистки кэша в windows с кодом:
Скопированоtaskkill /f /im explorer.exe
Скопированоcd /d %userprofile%\AppData\Local\Microsoft\Windows\Explorer
Скопированоdel /f /a:s IconCache*
Скопированоdel /f /a:s thumbcache*
Скопированоdel /f IconCache*
Скопированоdel /f thumbcache*
Скопированоattrib -h iconcache_*.db
Скопированоdel /f IconCache*
Скопированоdel /f thumbcache*
Скопированоcd /d %userprofile%\AppData\Local\
Скопированоattrib -h IconCache.db
Скопированоdel /f IconCache.db
Скопированоstart C:\Windows\explorer.exe
и для меня все работает как надо, но я не понял:

либо прописать в vbs-скрипте удаление/переименование предыдущего ярлыка и создание нового с новой иконкой

Скрипт вить просто удалит файл ярлыка а не его хэш, как это может работать?
Просто если прописать в скрипте удаление хэша то при запуске ярлыка будет перезапускаться  весь проводник start C:\Windows\explorer.exe, что очень не приятно...