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.
Plesk Panel 9.5 is extremely old software. Its support will soon be terminated by vendor. If your provider can upgrade you to more up2date version like 10.x or 11.0, you can solve the task very easy - there is a textarea to copy/paste all your recipients (just one recipient per line)