Each database (and in fact each table and even each column) can have its own collation for storing data, but (as far as I understand) the actual transfer of data to/from the database takes place using a specific collation. I
think this is determined by the incoming client connecting to MySQL, so long as the MySQL server supports what it's trying to use. (As you can imagine, a restrictive connection collation can result in data problems if it's stored differently).
It certainly looks as though you would be totally fine if your database was on your Moodle server, but I can't really tell about the remote server.
I assume you've already created your Moodle database on your remote server? Access that database through
phpMyAdmin, click the "Operations" tab at the top right, and somewhere on there (location depending on which version you are running) should be a "collation" section, with a drop-down box. The current collation of your database should be listed by default, but you can change it (click the "Go" button to do the change).
You basically want "utf8_general_ci" or "utf8_unicode_ci". If you can't select either of those, try
anything starting with "utf8"... and if that fails, then I'm afraid your database won't support Moodle properly.
Hope it works, 'cos I'm all out of ideas after that!