The way you are utilizing MSMQ is really circumventing some of the fundamental features of the technology. If queue message cannot be universally handled by the reader, you are incurring a pretty sizable system performance penalty, where many of your task processing services can get sent back empty-handed when they ask for tasks. In extreme scenario, imagine what would happen if there were only one service that could perform task type "A." If that service were to go down, and the first task to be pulled out of the queue is of type "A," then your entire system will shut down.
I would suggest one of two approaches:
- Utilize multiple queues, as in one per task version. Hide task retrieval behind an API or some other service. Your service can request a task from one or more task types, or you can even allow for anything. The API would then be charged with figuring out which queue to pull from (i.e. map to a specific task type, pick one at random, do some sort of round robining, etc.)
- Opt for a different storage technology over queueing. If you write good enough SQL, a relational database would be more than up for the task. You just must exhibit a lot of care to not incur deadlocks.