Maybe I don't fully understand the problem, but why can't you just match everything except what is inside the parens? You can verify that whatever within the parens is relatively insignificant by comparing the subject length before and after extracting the "random" string.

If the "random" string falls at the end of the message but isn't within parens, find out how much of the subject matches from beginning. Again, if the "random" string is much smaller than the matched portion, you can be relatively certain of success. Ignore this if I'm totally off base, I haven't had my coffee yet.

--Jim