A different (and, I suspect, more efficient) way to handle this would be to use another negated character class instead of the non-greedy modifier:

while ( $string =~ m!(<a[^>]*>)([^<]+</a[^>]*>)!ig )
[download]

(Personally, I'd make that [^<]* instead of +, just in case you get data with links <right><up><against><each><other>, but that's your call.)