Your regex doesn't work because your string $PrevMsgLink contains characters that are special in regular expressions, notably the pair of parentheses. You can use \Q...\E to prevent those chars from being interpreted as regular expression special characters:

my $topic_obj = $mech->find_link (text_regex => qr/\Q$PrevMsgLink\E/i 
+)
    or die "Didn't find anyhting matching '$PrevMsgLink' in the page!"
+;
[download]

But what you really should do instead of scraping the eBay website is to use the Net::eBay API, which gives you fast, robust and convenient access to all of eBay, within the limits of the eBay Terms of Use.