The MSDN article Synchronous and Asynchronous Operations explains what options are available to you when using WCF. It even tells me that svcutil.exe has an /async switch. Great!
Now, back to my current home turf, Compact Framework. There is netCFsvcutil.exe, that comes with the Compact Framework Power Toys 3.5. Guess what? That option isn't available in this scaled down rendition of svcutil.
Once again Compact Framework makes it so much harder to work productively, and here's why:
http://msdn.microsoft.com/en-us/library/2e08f6yc.aspx
Quote: Asynchronous delegates, specifically the BeginInvoke and EndInvoke methods, are not supported in the .NET Compact Framework.
Back to the drawing board and the thread pool (most likely).