Message-submitting clients used SMTP libraries. Message-consuming clients used Exchange APIs. Consumers would only look at unread messages, they would mark messages as read when they started processing, and move them to a folder other than the Inbox if they succeeded. Many of the queues were multi-producer, but all queues were single-consumer (CPUs were pricey at the time - our servers were all Pentiums and Pentium Pros), which simplified things a lot.
Need a new queue / topic? Add an email address. Need to inspect a queue? Load up an email client. An unexpected benefit was that we could easily put humans in the loop for handling certain queues (using HTML in the messages).
It worked surprisingly well for the 5 years that the company was around. Latency was okay, but not great. Throughput was much better than we would have hoped for - Exchange was almost never the bottleneck.