Redirect with init() action

I am working on GD Star Rating plugin, and I have a lot of problems with redirecting. I am not using AJAX yet. Here is what I am trying to do:

When a visitor votes, he clicks on a star, and the browser is directed to another page, actually the same page with additional query string parameters. If the page where the user was is:

clean: https://localhost/wpt/?paged=2

voting url will be something like this:

voting: https://localhost/wpt/?paged=2&gdsrvotes=8&gdsrtype=a&gdsrid=43&gdsruser=1

I have added init action that is used to save vote to database based on query parameters, and after that I need to rediredt back to the original url. But both wp_redirect and header functions don’t do it right. I try redirecting to a url withouth query strings and still after redirection I land up on the page with full voting query.

I have tried then to do redirections with some other actions, and redirect works if I add redirect code in get_header action. On the other hand this is not working right with some themes, since this action is connected to get_header() function call in the theme. And with some themes, I get error that output has already starred, and redirect is not working.

How to make wordpress redirect to a url in init action to be sure that no html output has been sent? Whay redirect is not working properly in the first place? I give the url, why I still lend on the wrong url?

Thanx,
Milan