I figured out what the problem was...
The bottom half of cron.php is what are called clean up tasks. There is a random number generator (from 0 to 100) and if the number is under 20, then these particular tasks will run. If it 20 or above they will not... so it's hit and miss as to when this section of the cron will actually run.
It so happened that everytime I tested it, that section did not run. I forced it to run those tasks as well, and it worked okay.
In order to make it run those tasks 100% of the time, change this line in admin/cron.php
$random100 = rand(0,100);
$random100 = 0;
And just as a side note: picking a random number to determine whether parts of the cron job should run or not seems rather odd to me. Would it not make more sense to timestamp when the last time these clean up tasks ran, and then let them run again every xyz number of hours/days since the last time? Then at least you would know that they are getting run regularly. These tasks include removing unconfirmed users and unenrolling longtimenosee students.