Is is possible for an Azure application to offer a service to end-users for carrying out long-running computation tasks that are going to be distributed over multiple Workers (with persistent storage)?
And would it be possible to provide this through a web-service that is accessed by a desktop .Net application (the View) or do you always need to use a web-interface with Azure?
Azure easily handles WCF-hosting, and you can make your WCF endpoint either internal (for just an Azure hosted app) or external (for a locally-installed app). Try this: create a new Azure cloud application, and add a WCF Service Web Role. This will essentially host WCF in IIS, and will provide you with what you're looking for.
Also look at my response here for information about a patch needed for WCF hosting.
Finally: about distributed processing: if your processing is done as an atomic action, yet you simply want to scale how many things you can process, this is very straightforward! You just create a worker role that reads from a queue and processes the next item. Then, your WCF service simply enqueues a request for work to be done. When the worker role completes the task and writes its results to storage, it reads the next request. You can then scale your number of worker role instances to process requests across a set of VM instances. If, on the other hand, you want to process an individual work item across several worker roles, you'll need to create some type of custom mechanism for instructing your individual worker role instances. For this, you'll probably need to set up internal endpoints on each worker role, and in your WCF service, divide up the request among the enumerated worker role instances, and then sending a direct message to each instance with its specific assignment.