When you uninstalled, did you make sure there were no Stellaris folders left in your drive?
IIRC, Stellaris leaves some of it's file-structure behind when uninstalled so it's likely that those have some modified file in there somewhere from a mod that's causing the checksum to be changed in some way.
I'm not at my home PC right now so I'm working from memory but if I'm remembering this correctly, Stellaris is located in both My Documents and in the steamapps folder under Program Files
Uninstall the game again, purge both of those locations of anything Stellaris related, reinstall again, and re-validate and you should be fine.