Oh multi-byte character encoding, you are the bane of so many developers. I love solving long standing problems.
So you’ve “SET NAMES utf8”, you’ve set “META character-set=utf8”, you’re sending UTF8 headers but you just can get rid of “Ã” characters. My solution was to clean everything that leaves the database with PHP’s mb_convert_encoding() function. Worked like a charm.
Now why this is even necessary in this day and age is a completely other story.