I think I 've found the solution! This bug is due to MySQL, I think. If the following sql query is executed: SET CHARACTER SET utf8 (without ; is recommended)
immediately after establishing a connection, the problem is solved, at least for me! Even more suitable query would be SET NAMES utf8, because connection's query strings are also submitted to the server in utf8.
<?php
$link = mysql_connect('localhost', 'database_username', 'database_user_pwd');
if (!$link) {
die('Could not connect: ' . mysql_error());
}
if (!mysql_select_db('database_name', $link)) {
echo 'Could not select database';
exit;
}

//could be also SET NAMES utf8
$sql = 'SET CHARACTER SET utf8';
$result = mysql_query($sql, $link);
...
?>
and instead of ... any query executed should return proper utf8 characters. Check this please in your environment!

The given fix works, if the database collation is utf8_* (f.e. utf8_general_ci).

However, querying a database with collation latin1_* still returns question marks instead of the actual characters. Thus, is it possible that PHP tries to convert any mysql results to utf8, even when neither the database/tables, nor the PHP files are in utf8 ?

I encounter this bug with PHP 4.4.7 on Windows (Server 2003). I'm not able to reproduce it with PHP 4.4.7 on SuSE Linux. Also, this bug does not seem to exist in PHP 5.

IIRC, my last installed version of PHP was 4.4.4, which did not have this bug.

Strangely, if I add the rather senseless line
<?php
mysql_query('SET CHARACTER SET latin1', $link);
?>
immediately after the database connect, all mysql query read/write results are fine.

I had the same problem with php 4.4.4 and MySQL server version of 4.1.22 standard on Linux server! Exactly, it is solved by this fix for utf8 char set when database char set is utf8. What is your MySQl server version? Maybe that's what matters.
Actually, by querying SET CHARACTER SET latin1 you did exactly the same fix! It seems we should apply the same char set in this SQL statement as in the database queried.
"Thus, is it possible
that PHP tries to convert any mysql results to utf8, even when neither
the database/tables, nor the PHP files are in utf8 ?" -> I think that is exactly what MySQL tries to do. Only I am not sure why it can not perform this conversion (according to this article at http://www.bluetwanger.de/blog/2006/11/20/mysql-and-utf-8-no-more-question-marks/ -> I think you should see it)
I 'll test this on php 5.x.x and post the results...

Do you experience the problem with PHP5?
PHP4 is no more fixed except for security updates.

I have not encountered the problem in PHP 5.x.x, but I think it also should be fixed in the manner described above...

We are sorry, but we can not support PHP 4 related problems anymore.
Momentum is gathering for PHP 6, and we think supporting PHP 4 will
lead to a waste of resources which we want to put into getting PHP 6
ready.