I don't know of any shared hosting company that would let you run a windows service - but shared hosts do let you run scheduled/reoccurring tasks.
Send the sales people of your top hosting choices an e-mail and ask them about reoccurring tasks (not windows services) and they will probably have something for you.
Back when I used http://webhost4life.com they had a way to add reoccurring tasks in their control panel - at a small extra cost, I never used it myself, I don't know how those tasks run and since I've left they replaced the entire hosting system (so I don't even know if this option still exists).