Resolution
Plesk Control Panel fully supports MySQL 5 since Plesk 8.1 version. It means that there are no point in Plesk code which conflicts with MySQL 5 and if you replace mysql4 with MySQL 5, it does not affect Plesk itself, all the SQL requests Plesk sends to MySQL from any Plesk's place will be processed without problems. There are no dependencies which do not allow mysql5 be installed.
If you are running Plesk version below than 8.1, you should upgrade to Plesk 8.1 first, then upgrade Mysql. Otherwise, if you upgrade MySQL to the 5th version on the server running Plesk 8.0.x or older, Plesk functioning and upgrade to further versions problems are possible.
Mysql 5 should be taken from the OS distribution and installed by means of the OS package manage in order to avoid possible dependencies conflicts.