It is kinda hard to put your comments into code that covers everything you wrote but I belief you guided me in the right direction:
mysql_set_charset('utf8');
I was doing all of this on a remote server where the issue occurs. This server still runs PHP 4 so I cannot test it. But it does the trick on my local server so I guess this is what was missing...?