My multisite (that's the new name for it; I believe MU is the term for pre 3.0) setup is subdomain. I don't know what difference that makes.
I just tried the code
$unsubscribe_link = esc_url( add_query_arg( 's2mu_unsubscribe', $blog_id ) );
$subscribe_link = esc_url( add_query_arg( 's2mu_subscribe', $blog_id ) );
and it works.
The query string doesn't need to remain the same. In fact, I tried stripping out the page=s2_users, and the subscribe/unsubscribe functionality still works and keeps me on the s2_users page automatically. It's just the URL that should remain the same.
I don't understand the part about not having a having a profile. If you don't have a profile, doesn't going to any Admin URL automatically send you to the login page? What does that have to do with Subscribe2?
I checked out the way things are done by Automattic. Taking a look at Akismet's configuration, I see that they use a POST form, even for just checking the "Network status".
You know what, this reminds me that a GET form that has side effects, e.g. subscribe and unsubscribe, is a bit dangerous.
Any form that can have risky behavior should use a POST with a nonce token, to prevent CSRF, as I believe you do in other forms.
Maybe that's the right way to fix the link anyway: just send the POST request to the current page with the s2_subscribe input tag.