I think you also need to grant access to a user in the right way. By default a database user created through Plesk is user@localhost and trying to login from a remote location would be rejected because they are not connecting from localhost.
So I think you need to GRANT xxx TO 'user'@'ipaddress' identified by 'password' for the database in question (or something like that --- I don't remember the syntax exactly).
xxx could be ALL but that's a security risk. You should limit it to what's needed rather than ALL. Using @'ipaddress' limits the connection to the static IP where the remote connection is coming from. I think you can also use a domain instead of an IP, and therefore control the IP via a DNS entry. You may also be able to grant to user rather than user@ but it would be more sensible to limit it to an IP if possible, even if your fireall only allows access to port 3306 from their static IP. Every extra level of security you add helps!
Have a look at the GRANT syntax to see what you can do. Like I say I can't remember the exact options off-hand.
Faris.