You might raise this question with support instead of here, since the answer to this question is largely based on internal architecture and design of the Force.com platform. Here's what I know, as well as what I think I know based on observations:

Apparent facts:

1) Workflows are processed every 15 minutes once the server starts (so, not necessarily at :00, :15, :30, and :45). It's been this way for a long time, unless they've finally changed it. This detail was in the webinar when they introduced time-based workflow rules.

2) There is a Workflow queue where instructions pile up awaiting their turn. You can see this queue in Setup for your organization.

3) Emails are not sent directly through SMTP, but are instead first queued into the email server for later delivery. Email headers from any salesforce.com support this fact.

Personal observations:

1) It appears that the time when a Time Delayed workflow rule executes might not be the same time that's logged. This is similar to the effect you see when you use a long-running Apex Class to generate records; the timestamps on these records will all be at the same time, and may be inaccurate by a minute or more. This also happens with the Apex Data Loader on large records in large record sets.

2) There appears to be at least two email queues, a "fast lane" and a "slow lane". Small, manually sent emails go through the fast lane, while larger manual emails and automatically generated emails go through the slow lane. This is why you can send an email to a contact after performing a password reset for a user, and the contact will receive the email before the password reset is received for the user.

Overall, if you need your emails delivered immediately, consider using an Outbound Messaging Workflow or a trigger with a callout to an external server, and make that server send the email instead.