Azure Service Bus Queue ScheduledEnqueueTimeUtc Delayed
From ScheduledEnqueueTimeUtc Property's documentation:
"Message enquing time does not mean that the message will be sent at the same time. It will get enqueued, but the actual sending time depends on the queue's workload and its state."
That property causes the message not to be delivered immediatelly. It won't be delivered before the set time, but there is not assurance that it will be delivered exactly at that time.
If you need high resolution scheduling, Quartz may be an option. You might also evaluate the new job scheduler that is part of the Mobile Services preview.
There was a recent regression in the ShcheduledEnqueueTimeUtc functionality that would in some edge cases cause the behavior you saw above. This will be fixed in the next couple days and you should see the expected/original behavior.
Scheduled messages can have some lag based on how busy the Queue is but is fine to use in the scenario you mention above. Any regression in functionality that affects your application can be raised as a support ticket with Azure: http://www.windowsazure.com/en-us/support/contact/