http://docs.moodle.org/24/en/Cron_with_Unix_or_Linux
shows how IF the hosting provider is running Linux. The link above shows how to test from the command line as a root user. If you have shell access you could test as well. Might have to ask the hosting support people to run the command line test.
The above link does show a 'wget' method as well as a 'curl' method for running the cron job. Those are like the browser running the cron.php link. If you are using one of those, is the cron job behind a password? See Site Adminisration Menu -> Security -> Site Policies
crontab is different in that it must run under the user of the apache service. From the link above:
"Using the crontab program on Unix/Linux
Once you have selected (and tested!) an appropriate command to invoke the Moodle cron it must be added to the web users 'crontab' to schedule it to run regularly. 'Crontab' is both a file containing the user's cron commands and is also the name of the (command line) program used to edit it. Use the following command (as root) substituting the correct user in place of 'www-data' (e.g. 'apache' for Centos, 'www-data' for Debian/Ubuntu - Google will know!)"
It would be unusual, but ... if php scripts do not have enough time to complete or enough memory allocated, those could also cause cron job to fail (it is a php script).
The page above also mentions "an alternate php.ini for the CLI PHP command which may not have suitable settings".
'spirit of sharing', Ken