Solution:
Adding the following rewrite rule finally fixed the issue.
RewriteCond %{QUERY_STRING} ^uri=(/[^&]+) RewriteRule ^nextgen-share/(\d+/\d+)/full$ %1#gallery/$1 [QSD,NE,R,L]