OK after investigating this is something you can't do in Plesk control panel but it can be done via SSH.
You can easily create email address using SSH using the Command Line Utilities for Plesk these are normally located in /PRODUCT_ROOT_D/bin and /PRODUCT_ROOT_D/bin/mail.sh
The mail command line tool supports:
- enabling or disabling mail service on a domain
- creating and deleting mail accounts
- editing mail account settings
- managing mail groups associated with mail accounts
- managing mail user control panel access
- managing mail user control panel interface parameters
So sadly this looks like your going to have to bash on at your provider and without offence if they can't do simple tasks as this then its time to reconsider them as a long term provider for managing your needs for your business because if this is headache what else is going to be?... You should be able to pass them that spreadsheet of the accounts you want created and they should be able to create a script which prefixes the commandlines to each email and simply batch creates them. It's easier than it sounds.