You can use MSMQ to provide shared queues between your applications, with one of the applications acting as the master; the Windows service would be the best choice if it's always running.
I use System.Data.Sqlite for communicating between Windows services and applications. Even though you said no databases, you might find this a worthy compromise. It's an embedded database with no admin burden. You "ship" it by including a single DLL in your applications, and it saves your data in a single file.
Think of it as a persistent file that you access using SQL statements via ADO.Net; it even sports a LINQ interface. You get locking through standard transactions (with rollback) and it also offers encryption. You can modify and view its contents using the Visual Studio Service Explorer. It works on .Net 3.5 and .Net 4. And it's open-source with no restrictions. You can add columns and tables without breaking existing functionality. Since deployment is as simple as adding a DLL to your solution, it's much easier to deploy and support. And since the connection string points to a file, it makes it easy to hit it from remote machines. Perhaps not as elegant as shared queues or mutexes, but its greatly simplified things for me.