Location redirecting problem

I was going through all the actions that WP executes from the start of the page, starting from init, trying to find the best place to execute redirection using Header function in php. The reason for needing the redirection in the first place is to remove query string from url added by Star Rating plugin.

If I try to do this in init action, I create url without extra query string elements, but after redirect, query string remains. My guess is that this is related to WP url rewrite.

If I try to do redirect in wp_head action, I get Cannot modify header information error.

The last thing I tryed, and for now it works is get_header action executed by the theme. Here, redirection works always as it should, and no header are sent yet, so no error. But this depends on the theme, and I know that almost 100% of themes have get_header call, I would like to find some solution that will work always.

What is the order of action leading from init to header, and when WP does url rewriting?

So, what is the best for me to try for redirect to work, and to avoid WP rewriting url after I have already created it?

Regards,
Milan