I think the problem is that the reschedule just adds it to the queue of all things already scheduled. We see the same delay here.
It would be nice if "schedule an immediate check" actually meant immediate rather than schedule.
I don't have that problem. It takes only less than a minute for a service check to execute when doing as you stated, i.e. reschedule and immediate check.
What version? Mine is V1.2
whatr's the machine load? possibly it's at 100% CPU fixed and it is not able to make the checks in the time it's scheduled for so they queue up.... just an idea