404 Error

I am having a serious problem with one of my sites. I recently bought the site from a friend and successfully moved it to my hosting. Unfortunately when I publish articles, and open the URL ( after successfully posting ) I get 404 error.

Example

http://premierleague365.com/end-theo-walcott-arsenal-plan-52m-julian-draxler-signing/

http://premierleague365.com/manchester-united-gets-massive-boost-paul-pogba-chase/

Also, this article here –http://www.premierleague365.com/man-united-gets-greenlight-complete-pogba-signing-madrid-pulls/

Is already deleted from the wordpress dashboard but is still showing on the site. I have contacted the hosting company and here is what they said

“Something with the way the website is
built is causing the 404, if it was the server, the entire page would
be displaying the 404. While it may be a server error though highly
unlikely, a developer or the CMS’s support would need to investigate
further to provide us where it may actual be that sort of issue.”

I don’t know what to do again. Can someone please advise me?

I don’t mind paying for the advise. I have been on this for more than a week now. I first thought it was propagation problem but was told that takes only 24-72 hours at most.