It would be impractical to manually sort the underlying vector after each addition/removal for the list. It would only be reasonable to do this if it were somehow possible to force vector::push_back() to automatically insert elements such that insertions preseve the sorting of the list.

What you're talking about here is an ordered insert. There are functions in <algorithm> that allow you do do this. Rather than using std::vector::push_back you would use std::vector::insert, and call std::lower_bound which does a binary search for the first element not less than than a given value.

auto insert_pos = std::lower_bound( L2.begin(), L2.end(), value );
if( insert_pos == L2.end() || *insert_pos != value )
{
    L2.insert( insert_pos, value );
}

This makes every insertion O(logN) but if you are doing fewer than N insertions between your periodic checks, it ought to be an improvement.

The zipping operation might look something like this:

auto it1 = L1.begin();
auto it2 = L2.begin();

while( it1 != L1.end() && it2 != L2.end() )
{
    if( *it1 < *it2 ) {
        Handle_Missing( *it1++ );
    } else if( *it2 < *it1 ) {
        Handle_New( *it2++ );
    } else {
        it1++;
        it2++;
    }
}

while( it1 != L1.end() ) Handle_Missing( *it1++ );
while( it2 != L2.end() ) Handle_New( *it2++ );

The while condition should use && instead of || since you only want it to continue if both lists still have more nodes. (BTW, you're over-using parentheses!)

int listEqual(struct Node *node1, struct Node *node2) {

    while (node1 && node2) {
        if (node1->data != node2->data)
            return 0;
        node1 = node1->next;
        node2 = node2->next;
    }

    return node1 == NULL && node2 == NULL;
}

Or recursively (but this is only reasonable if you're guaranteed tail call elimination such as with gcc -O2):

int listEqual(struct Node *node1, struct Node *node2) {
    if (node1 == NULL && node2 == NULL)
        return 1;  // If both are NULL, lists are equal
    if (node1 == NULL || node2 == NULL)
        return 0; // If one is NULL (but not both), lists are unequal
    if (node1->data != node2->data)
        return 0;
    return listEqual(node1->next, node2->next);
}

Firstly, you probably want to compare the contents of the iterators and not the iterators themselves

if (*begin_this_ == *begin_other_) ...

Secondly, you return 0 whenever two iterators compare equal which means you exit the loop.

I suggest you return early only if two elements are NOT equal.

Sadly, you have not described what value is returned if the sizes are equal but the contents are not, so I will assume that the elements are less than comparable.

Then your while loop will look like

while (begin_this_ != end_this_) {
    if (*begin_this_ < *begin_other_)
        return -1;
    else if (*begin_other_ < *begin_this_)
        return 1;

   ++begin_this_;
   ++begin_other_;
}

// end of loop which means that all elements are equal
return 0;