The solution was mentioned in this thread https://www.nopcommerce.com/en/boards/topic/92720/plugin-development-4404-install-issue/page/2, for versions under 4.5 you need Visual Studio 2019 and you have to do a full Clean + Rebuild, which will work. If you are switching between 4.5 and lower ones you have to check if the rebuild was done successfully as I had some issues with some plugins and had to manually rebuild them.
For 4.5 and onwards you need Visual Studio 2022 and do the same steps as above.