Custom loops, sticky posts, and pagination nightmare

Question

I've tried everything. I've looked at every. single. question. here, on StackOverflow, the WP help forum, googled 10 pages deep and literally tried EVERY combination of code I could find, for the last 2 days, and can't get anything to work how I want it. Surely it can't be impossible? The goal seems so simple!

THE GOAL: Show ALL sticky posts first, and then normal posts after them - WITH PAGINATION.

Example: With posts per page set to 10, having 15 sticky posts and 15 normal posts, page 1 would be 10 sticky posts, page 2 would be 5 sticky posts and then 5 normal posts, and page 3 would be 10 normal posts. Ordered by date.

I've tried multiple loops, various queries, and have come CLOSE but so far no cigar. Here's what I have so far:

<!-- THIS CODE QUERIES ALL POSTS AND RETURNS ONLY STICKY POSTS, DISPLAYED AT TOP OF THE PAGE -->
<?php
// show only ads within this specific category
$term = get_term_by('slug', get_query_var('term'), get_query_var('taxonomy'));
//$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
$sticky=get_option('sticky_posts');
$args=array(
    'post_type' => 'my_custom_post_type',
    'ad_cat' => $term->slug,
    'caller_get_posts' => 1,
    'post__in' => $sticky,
    'posts_per_page' => -1
    //'paged' => $paged
    );
query_posts($args);
?>
<?php get_template_part( 'loop', 'post_featured' ); ?>
<?php wp_reset_query(); ?>

<!-- THIS CODE QUERIES ALL POSTS AND RETURNS ONLY REGULAR POSTS, DISPLAYED BELOW THE STICKIES -->    
<?php
// show only ads within this specific category
$term = get_term_by('slug', get_query_var('term'), get_query_var('taxonomy'));
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
$sticky=get_option('sticky_posts');
$args=array(
    'post_type' => 'my_custom_post_type',
    'ad_cat' => $term->slug,
    'caller_get_posts' => 1,
    'post__not_in' => $sticky,
    'paged' => $paged,
    );
query_posts($args);
?>
<?php get_template_part( 'loop', 'post_normal' ); ?>
<?php wp_reset_query(); ?>

The above shows ALL sticky posts and then (5) normal posts. This is the closest I have gotten, but #1, I don't want to show ALL sticky posts on the first page, I want to adhere to the pagination rules. #2, ALL sticky posts show up on all paged pages. So if I have 50 sticky posts and 50 normal posts, each page shows 55 posts - the first 50 are the sticky posts and the last 5 are normal, which is not my goal (see THE GOAL above).

Is there an easy modification to one or both loops? Should I be using a double loop or is there another/better option to do this? I'm open to suggestions as long as I get it to WORK. I should note: I'm using WP 3.2.1 and a slimmed down non-plugin pagination function which was taken from WP-PageNavi (full pagination function can be seen here: http://paste2.org/p/1596821).

Any help is appreciated!