Message queues are widely used to connect loosely coupled components to form large-scale, highly distributed, and fault-tolerant applications. A number of vendors currently provide cloud-based queuing services that are designed to be elastic, scalable, and easy to use. However, unlike enterprise queuing systems, which provide strong queuing consistency and are suitable for many traditional enterprise workloads, these cloud-based queuing services offer reduced queuing consistency. They can deliver messages without loss, but they may deliver messages out of order or with duplications. This paper presents SilverDove Queuing Service (SDQS), a scalable cloud-based queuing service with stronger consistency than existing cloud-based queuing services. SDQS delivers messages without losses or duplications and provides in-order message delivery as an option. Built on top of IBM WebSphere® eXtreme Scale, i.e., an elastic in-memory object grid system, SDQS can be easily scaled up and down to accommodate a wide range of workloads. SDQS is able to provide high availability with either the no-order or the in-order message delivery option. We have performed a preliminary evaluation of SDQS with up to 70 nodes on a compute cloud platform, verifying its consistency offerings and providing insights into the tradeoff between performance and consistency.