What is your deployment tool?
"We ended up deleting everything from the WebApp folder, except App_Data and some WebSite folders".
Can you explain details your solution? We will use a FTP tool to connect to Azure server and delete all files (web.config, global.asax,...) and folder and only keep App_Data and folder that start with "CMS", right?
Do you have other solution? It seem this solution is not safe.
I have check version of CMS.Core in "bin" folder and it is "9.0.5809.18510" so I think the project did not reference to it.