Weird characters, encoding mismatches

Weird characters, encoding mismatches

I'm having this weird problem where characters are appears as symbols such
as: Ã ° Â
Sometimes this error occurs for other times not like so:
(¯`'·.¸[ ~ ]¸.·'´¯)
is converted to
(¯`'·.¸[ ~ ]¸.·'´¯)
I've set the mysql_set_charset to utf8, the HTML meta is set to output in
UTF8, the column collation that I'm adding this data to is set to
utf8_general_ci. In fact if I view the data in the database it looks
perfectly normal.
Sometimes I started making use of utf8_encode() because in the case of all
those characters, on entry to the database it was cutting short and only
entering the first parentheses e.g. ( One particularly weird thing is that
if I use utf8_decode on the (¯`'·.¸[ ~ ]¸.·'´¯) then it looks
normal. However if I use utf8_decode for all the data in the table then
that starts outputting ð�� instead of à ° Â
Edit
I should note that the text is coming from e-mails so perhaps the issue is
that the encoding is all mashed up? It is odd that it appears okay in the
database though...
I have read some similar issues on here but failed to understand them and
this case seems particularly weird... What do you advise is the problem
here?