Very strange problem with permalinks

I can’t make any sense of this at all. I have about 15 websites I maintain. 10 of them use the same theme-no problems at all with permalinks set to /%postname%/. One site for some unknown reason has decided to be difficult and give me a “page not found error” when linking to posts.
I completely deleted wordpress and my account.Reinstalled my account and wordpress from fresh and bang, same problem. What the…??? How is this possible when 10 other sites are using the same theme?

The ONLY thing that is different is that this one is being hosted in a separate company.

Any ideas how to fix this screwball issue?
Thanks