Hi Swannie

Have you checked the
Email and Newsletter Marketing forum? There are many discussions there about which programs are favored by various VAs.
I've worked with Constant Contact (VERY bulky and kind of a pain when it comes to customizing newsletters) and Vertical Response (very easy to write custom-coded newsletters) - both have numerous ready-made templates you can work with as well. Both charge based on the number of emails you send, I think Constant Contact also might charge a monthly fee.
There's a
blog post here that might also help point you in the right direction. It mentions Mad Mimi, Mail Chimp, etc. as well as Constant Contact.
As to the need of a French-compatible software I would imagine that you can write most special characters in most of the softwares out there and the helpdesk at whichever one you choose would also be available to help with that kind of issue.
I hope this helps!