Since you want parallelism with your PlayMessage, i would suggest looking into TPL Dataflow, as it combines both parallel work with async, so you could await your work properly.
TPL Dataflow is constructed of Blocks, and each block has its own characteristics. Some popular ones are:
ActionBlock<TInput>
TransformBlock<T, TResult>
I would construct something like the following:
var workItemBlock = new ActionBlock<WorkItem>(
workItem =>
{
PlayMessage(workItem);
Console.WriteLine("Works on {0}", workItem.TaskID);
OutLog.Write("Works on {0}", workItem.TaskID);
}, new ExecutionDataflowBlockOptions
{
MaxDegreeOfParallelism = // Set max parallelism as you wish..
});
foreach (var workItem in OutputQueue.GetConsumingEnumerable())
{
workItemBlock.Post(workItem);
}
workItemBlock.Complete();