Custom loops, sticky posts, and pagination nightmare

@Chris_O is right… currently sticky posts are not supported in custom post types so it must have something to do with the theme you are using.

Now disregarding the CPT problem… and assuming that it does work the same way wordpress stickies do then the goal that you are describing is exactly the way ‘sticky’ posts are designed to work in wordpress (i.e. show all the sticky posts before showing the normal posts and adhere to pagination), so from what I can tell your problem lies in the fact that you are trying to create two separate loops. In order to display the posts they way you want them to be displayed you should be using only one loop.

Have you tried just running one loop (i.e. removing the second query and replacing the first one with something like the below to see if the stickies are automatically added)?

$paged = get_query_var( 'paged' ) ? get_query_var( 'paged' ) : 1;

$args=array(
  'post_type' => 'my_custom_post_type',
  'paged' => $paged,
  'posts_per_page' => 10
);
query_posts($args);

get_template_part( 'loop', 'post_normal' );