Most people read from left to right, so In my opinion the flag or star icon should be definitely on the left.
In MS Office it's on the right, but there is an exclamation mark on the left (which has a similar function) - so in this case it seems okay:

In Yahoo Mail - there's only a flag option on the right - I think in this case it should be on the left side, because on the right users hardly notice that they have 'flagged' a massage - so it is ipmortant:

Gmail uses a 'star' icon on the left. In my opinion this is the best solution. It's on the left, easy to see, attracts attention.

Anyways what kind of function do you associate with flagging/starring a message? And where would you place the icon?
In my head it means the message is important! I have to deal with it some time! "To Do"