Why are you considering providing an asynchronous API?
Are the API operations IO bound or CPU bound? (is the reason it takes a long time because of waiting for IO to complete, or just it's CPU intensive?)
If CPU bound, I would consider whether it really is necessary to provide an asynchronous version, since the caller can always effectively convert a synchronous operation into an asynchronous operation via the threadpool.
The strongest reason for providing an asynchronous API is for operations which are IO bound. Rather than tying up threads to wait on high latency IO operations it is preferable that asynchronous IO is used. This can particularly affect the scalability of a system. For example, if you had a server blocking on a single synchronous IO operation, it's not too much of an issue - you're just tying up one thread. However, execute 1000 of the same operation concurrently and you're tying up 1000 threads (and if memory serves 1MB per thread for stack) just to wait on completion of operations which take few CPU cycles. End result - you've got an idle CPU but are sucking up resources.
So, if for example, you yourself were writing a socket library, for sure you would want to provide asynchronous IO operations, so that users of the library could write scalable applications.
If, for example, you're writing an encryption library, then even though the operations may take a long time, there's probably no pressing need to provide an async API - it's CPU bound anyway. And as mentioned the user can make it asynchronous.
Finally, if you're writing an IO bound system which uses lower level APIs that provide asynchronous IO (e.g. an FTP client that uses the socket classes) you may also want to consider providing an asynchronous version of your API. The thing is though doing this isn't easy - you only provide the scalability benefit if you make use of the lower level API's asynchronous functions. This can quickly end up turning simple synchronous logic into extremely complex, difficult to debug asynchronous logic. The main issue being all the state information you previously had nice simple access to via local variables end up needing to be manually captured so that when the next IO operation completes your logic knows what to do next.
Providing an asynchronous API which then makes calls internally to synchronous IO operations is kind of pointless (though I've seen it done). Gives the illusion of scalability, but... isn't!
When .NET 4.0 comes out, some of this may get a bit simpler (though I think from what I've seen it's still going to be tricky).
In the mean time, you might want to check out Jeffrey Richter's async enumerator library which can help simplify this (somewhat):
Jeffrey Richter on his async enumerator
Power threading library including async enumerator
Hope this helps,
Phil.
NOTE: If you are going to implement an asynchronous API, I would recommend providing it via the 'classic begin/end' IAsyncResult API. The reason is, from what I remember, it should integrate much better with .NET 4.0's task parallel library.