If moving to C# 5.0 is not an option, then I am afraid you will have to fallback to the more traditional approach of using callback functions. I once migrated a thick client application using this approach.
Every application is different so it is hard to predict how much rewrite you'd need but in my experience, it was never overwhelming. What took more effort was the gotchas that come with asynchronous programming. I can highlight two:
First and foremost, you'd need to think about your application flow and figure out which parts of the application should remain disabled when an async operation is running. If an application has not been designed with this in mind then it can take a lot of effort to maintain state information and logically grouping the sections that should go disabled together etc. If your application is a server, then you may not run into this complication.
Second, and this has universal applicability, you will need to come up with a way to recover the information
BeginAsync(...) calls. One way to do this is to pass the
function and its arguments in the call back object itself. You get a
reference to this object in the
EndAsync(...) method. An obvious
gotcha there is to make sure you are able to distinguish one
BeginAsync(...) call from another one on the same method.
I am not saying that you can avoid thinking of these issues with the newer API. These are common issues with async programming in general --in any framework or language. But once you write some async code and get it to work correctly, it becomes second nature to think this way.