We are designing a system where the business calculations will be encapsulated in CRM plugins which are called from a workflow in CRM.
Many of these business calculations are in legacy systems in several different technologies.
Question is: Do we have to move this code into the plugin as C# code, or can we call it via a web service from the Plugin?
A custom workflow plugin is a Windows Workflow Foundation activity. Whatever you can do in a workflow activity you can do as a workflow plugin - so, the answer is yes. However, you may want to give configuration parameters as input to the workflow activity (ie. the URL to the service) or store it in a custom entity. This way everything can be configured from CRM. You can even export the workflow xaml, modify it in a designer and reimport it into CRM. In CRM 2011 this is even a supported approach (so they say). Note that for CRM online, custom workflow activities are not supported.