It sounds like you need to normalize first, then extract. So, maybe the first thing is to $string =~ s/_/ //g; to convert all the underscores into spaces.

Another strategy could be to get rid of all the things you can easily identify. So, you know where the file extension (.mkv) is, so get rid of it. The BCCEA15E, the VORBIS, and the "- 07" can all also go. Then, you're left with a much smaller thing to work with.