The default "Sending..." notation blocks you on the same page, doesn't it?
It doesn't block the UI and yet it still gives the user an indication when the actions are in progress/completed.
So instead of blocking and showing the "Sending..." message, it redirects you to the main inbox and shows a "Sending in background..." message, until the message has been sent. Of course, Gmail is so fast for me that usually I'm barely back at the inbox before the message is finished! :)
While your point about the server-end being a queue is true, there's an expectation once your message is offloaded onto Google's queue, they will reliably process the message in a reasonable amount of time.
So the idea is that instead of time-consuming, blocking operations, you have fast blocking operations that put things in queues, and the queues then handle the slow operations.
as soon as you send a message, it goes into a little list on the side of your screen of things that are transferring to Google's servers. You can see it there, and you will see it go away when it has been transferred, so you know what's going on. But in the mean time, you can go back to your inbox, look at other emails, or do whatever else you want. That's how an asynchronous interface should be done.
One thing I didn't notice the article mentioning is that it's possible to have blocking only for certain parts of an interface. So if you press a "load picture" button, then maybe a gray square with a spinner will appear, but the rest of the interface should continue working as usual.