Hello,
I tried everything that you suggested and much much more but nothing worked.
I stumbled across https://superuser.com/questions/1261293/missing-icons-for-trusted-microsoft-store-apps-in-start-menu-search-and-taskbar which describes my exact issue.
I tried the following on the off chance... (I didn't have Google Drive for desktop installed either)
Adding to the answer by @Nate - interestingly for me it worked after installing Google Drive for desktop from this place: https://support.google.com/drive/answer/7329379. I never had installed it earlier, so there was no need to uninstall it, but installing it resolved the issue magically! I then uninstalled it and the icons still show up, no problem at all :). Also found a GitHub page somebody created, it might be interesting for some: https://support.google.com/drive/answer/7329379
IT WORKED!! I have no idea how or why but all my trusted apps icons are back and they also work in my taskbar.
Thanks