MsmqAsyncSpike.cs

namespace MsmqAsyncSpike
{
    using System;
    using System.Messaging;
    using System.Threading;
    using System.Threading.Tasks;

    class Program
    {
        static void Main(string[] args)
        {
            var queue = new MessageQueue(@".\private$\asyncspike");

            StartMessagPump(queue)
                .ConfigureAwait(false)
                .GetAwaiter()
                .GetResult();
        }

        static async Task StartMessagPump(MessageQueue queue)
        {
            while (true)
            {
                await Task.Factory.FromAsync<Message>(queue.BeginPeek(), queue.EndPeek);

                Task.Factory.StartNew(() => ProcessMessage(queue))
                    //todo: add our custom scheduler here so we can control: 1. Threads, 2. Throughput (if requested by user)
                    //todo setup onfaulted?
                    .ConfigureAwait(false);
            }
        }

        static async Task ProcessMessage(MessageQueue queue)
        {
            Func<Message, Task> pipe = m =>
            {
                Thread.Sleep(10000);
                Console.WriteLine(m.Id);
                return Task.FromResult(0);
            };
            
            using (var tx = new MessageQueueTransaction()) //use a native TX in this sample
            {
                tx.Begin();
                
                //there is no async version of receive http://stackoverflow.com/questions/16100773/messagequeue-and-async-await
                var message = queue.Receive(tx);

                await pipe(message);

                tx.Commit();
            }
        }
    }
}

Andreas, I would instead pump the receive via an IObservable, something like:

class Program
{
    static void Main(string[] args)
    {
        var queue = new MessageQueue(@".\private$\asyncspike");

        new Program().StartMessagePeek(queue)
            .ConfigureAwait(false)
            .GetAwaiter()
            .GetResult();
    }

    private Observable<Message> pump = new Observable<Message>();

    async Task StartMessagePeek(MessageQueue queue)
    {
        while (true)
        {
            await Task.Factory.FromAsync<Message>(queue.BeginPeek(), queue.EndPeek);

            Task.Factory.StartNew(() => ProcessMessage(queue));
        }
    }

    void ProcessMessage(MessageQueue queue)
    {
        using (var tx = new MessageQueueTransaction()) //use a native TX in this sample
        {
            tx.Begin();

            var message = queue.Receive(tx);

            pump.OnNext(message);

            tx.Commit();
        }
    }
}

How to do a single thread message pump for a console app.
http://blogs.msdn.com/b/pfxteam/archive/2012/01/20/10259049.aspx
http://blogs.msdn.com/b/pfxteam/archive/2012/01/21/await-synchronizationcontext-and-console-apps-part-2.aspx
http://blogs.msdn.com/b/pfxteam/archive/2012/02/02/await-synchronizationcontext-and-console-apps-part-3.aspx

Thanks @distantcam will look into that