First, while .NET is pretty good performance-wise, if very high performance is a basic requirement, I would turn to a native-compiled, unmanaged language like C++. JIT compilation and the other overheads of the CLR are going to slow down the performance of any algorithm written in .NET.
I think that thousands of truly simultaneous requests are going to indicate a highly distributed model; right now, the best server hardware on the market (dual Xeon quad-core hyperthreading CPUs) will only do 32 things at once, and listening for requests to do things, talking to the hardware layer, and other general OS/runtime overhead will take up a couple of those. I would analyze the real traffic you expect this server to handle concurrently, and scale the number of boxes you have working on it to match.
Second, I think that you're talking about when you say "I/O completion threads" are the threads that the asynchronous Begin/End calls use to do their job, instead of threads from the ThreadPool (avoid in really thread-heavy apps) or user-created threads (no problem with these, just watch your thread count). Really, except for a few special cases, a thread is a thread, and exactly where it's spawned doesn't make much difference at the hardware level, so if you really wanted to, spawning worker threads that used the synchronous calls would get you pretty much the same result (but it's generally better to use the tools you have rather than forge new ones).
Now, to your real question. No, there is not an asynchronous model for hashing; if you want to multithread a hashing operation, the thread must be spawned seperately. However, hashing requires a stream or byte buffer, which can be obtained asynchronously using Stream.BeginRead(), and the callback method passed to BeginRead() can perform the hashing in the thread that the asynchronous call spawned.