I personnally clear my Temp Internet folder out daily. In fact, I use firefox, and use an extension that allows me to clear the temp folder any time with one click. On some internet connections cleaning it out may affect your speed, simply because it stores pages that you have visited. However, if you have DSL or Cable, you are not going to notice a significant reduction in surfing speeds.
I have put this to the test on a few occasions, and personally would rather have a nice clean temp internet folder mainly for the reasons of privacy. Also, if you visit a lot of pages that have video or images, these can take up a bit of space on your hard-drive. So all in all, it is just about your personal preference, but if you are wanting my advice, and you don't spend 14 hours a day as I do on the web, you may consider cleaning it out every 2-3 days.
It is true that when running cleaner apps that sometimes conflicts arise. But as in your case, usually these problems have a way of sorting themselves out. That is why I recommened Cleanup! It does a good thorough job, but isnt to harsh on your files.
Hope this helps,