wp_rewrite not working on third level url

Your regex is a little flaky – you shouldn’t specify the start anchor ^, and some support trailing slashes, others don’t – plus I’d opt for a better expression for matching page numbers. And you could certainly trim it down to:

add_rewrite_rule(
    'activate/([^/]*)/?$',
    'index.php?pagename=activate&akey=$matches[1]','top' );

add_rewrite_rule(
    'users/?$',
    'index.php?pagename=users','top' );

add_rewrite_rule(
    'users/(most-active|recent|oldest|by-username)/?$',
    'index.php?pagename=users&sort=$matches[1]','top' );

add_rewrite_rule(
    'users/(most-active|recent|oldest|by-username)/paged/([0-9]{1,})/?$',
    'index.php?pagename=users&sort=$matches[1]&paged=$matches[2]','top' );

I noticed that by-username translates to the sort parameter byusername – if the sorting logic can’t be changed to accept the hyphenated value (which I recommend for consistency), add a separate, specific rule-pair.

If you’re still having problems, load the request and print out $wp->matched_rule – this’ll tell you which rule WordPress hit & proceeded to handle.