Nutso,
Nobody has replied to you so I'll give you the bad news. The payroll legislation, rules, procedures, calculation process, etc., etc. varies greatly from country to country. So, it would not be possible to develop a payroll software solution that catered for the requirements in multiple countries simultaneously. We do payroll software for Ireland and the U.K. and, while the applications look SIMILAR from a user's perspective, the "engine" that calculates tax and social insurance is completely different in both.
Your best option is to go for a low cost solution from each country or, even better, farm out the payroll in the other European countries to a bureau.