I've coded precisely this kind of Windows service, and I think you're on the right track. I use a database table for my queue, which gives me a persistent queue in case of a system crash, readily allows multiple writers from across the local network, and lets me manage contentions through transactions.
I create separate threads for each process and keep track of the number active threads, which lets me adjust on the fly. Since each thread makes a web service call, there was negligible benefit from using the threadpool, and this also allowed me to start a lot of threads since they blocked waiting on an external server.
It's easy to manage if you allow only one reader, thus allowing you to keep track of the queue entries you've read by just using an identity column and selecting the next one higher than the last one. As a thread finishes it can delete the entry it was working on.
If your service crashes it will just pick up with the first unread entry. You can get fancier by including a column that indicates when the entry was touched, and if the processing fails (perhaps due to a network timeout) then you can untouch it and let it get caught by the next read. If you need to have multiple readers then use a timestamp field that indicates when it was touched; one reader can recover for another crashed reader by checking when an entry was touched.
You should also trap the service-closing event so that you can finish processing cleanly, and include your own logging so that you can trace what's happening once you get several simultaneous writers.
Also consider a test version that lets you hammer your queue reader and measure how it bears up under load. This will go a long ways to helping you weed out the not-so-obvious gotchas that lurk in a multi-threaded application.
But I had a blast creating this and I hope you do, too.