I must admit sometimes it is useful but i realy dislike it.
Yes. There are several cases in which this is hugely beneficial - in-text links that may duplicate others, links in large lists for which the user might be expected to visit several, links to anything that could be considered an 'object' in a 'set' (e.g. users in a social network), etc.
In main navigation, I don't think it's particularly useful. And it shouldn't be used to mitigate poor usability associated with bad link labelling (links should usually be labelled as closely as possible to the page they link to). The fact that visited links are 'forgotten' after a while is a shame, but this functionality is most useful during a session anyway.
Sure. Simply because we, humans, don't read we scan, at least this is the first action we take, then, when we think we found what we want we (may) verify it by reading. Hence, visual differences help us get what we want, in this case - go back to where we visited before. I bet you prefer looking for a different colored text then have to thoroughly read the whole page, or finding yourself try to remember - where was that link that took me there?!#@!?
Yes. I think it should change, because it helps users browser your entire site. I don't know many users that commit "previous pages" to memory.
I think you need to provide more context to really have a good answer.
The commonly held opinion is yes, you should, because it is an important usability issue. I think if you had to go to one way or the other, including visited indication of any sort is beneficial to the user.
I think designers struggle with this issue, because it means it is something else that have to design to look good, and it is hard to make randomly visited links look good.
I, personally, think it is important, in particular, for content heavy websites. If you are browser through a long list of items on a sidebar, it is nice to know what you've visited. However, in cases where you might have 4-6 links in your top navigation, most users will be able to tell where they've been.