CiviCRM reports Cron not running, but my web host is adamant that it is
I think you probably will need to provide full path of php to execute php files. 

You can try the option from https://stackoverflow.com/questions/19916949/running-php-from-cron-did-not-run-as-cli/19917512#19917512

HTH

Pradeep