What you describe is not an issue but normal WordPress behaviour. When you mark a post as a sticky it will be at the top of the list and it will appear in it's original postition as well, unless the original position is on the first page. A sticky will appear at the top of the posts and in it's original position but it will not appear twice on the same page.
You might want to do something like this:
<?php
while (have_posts()) : the_post();
if ( !in_array( $post->ID, $do_not_duplicate ) ) { // check IDs
// display posts ...
the_title();
//store id in "do not duplicate
$do_not_duplicate = $post->ID;
}
endwhile;
?>
source with minor edit: http://wpengineer.com/1719/filter-duplicate-posts-in-the-loop/