I doubt you can do that with just a single regex. Even if you come up with something it'll be ugly.
Here's how I would approach your problem:
use strict;
use warnings;

my $folder = $ARGV[0] ? $ARGV[0] : '.';
my $file;

opendir DIR, $folder or die "Can't open $folder : $!\n";
while (defined($file = readdir DIR)){
    next if $file eq '.' or $file eq '..';
    $file =~ tr/_\t\r\n;:/ /;
    $file =~ s/\s+/ /g;
    $file =~ s/- *(?:track *)?\d+ *-/-/gi;
    $file =~ s/^\d+ *- *|^\d+ *\. *|^[(\[{] *\d+ *[)\]}] *//;
    $file =~ s/(\S)-(\S)/$1 - $2/g;
    $file =~ s/(\w+)/\u$1/g;
    print "$file\n";
}
closedir DIR;

[download]
As you can see, the code just print()s the "beautified" version of each file name. You can replace print() with rename() or whatever you like.

Input 
01-Paul_Oakenfold_-_01_-_HHC_-_We're_Not_Alone.mp3
04.Paul_Oakenfold_-_04_-_Red_Sun_-_This_Love.mp3
05. Paul_Oakenfold_-_05_-_Ryuchi_Sakamoto_-_Little_Budha.mp3
Paul_Oakenfold_-_Track 06_-_Man_With_No_Name_-_Teleport.mp3
Paul_Oakenfold_-_07_-_Terrorvision_-_Conspiracy.mp3
Paul_Oakenfold_-_08_-_man_with_no_name_-_Sugar_Rush-retry.mp3
Paul_Oakenfold_-_09_-_Eric_Serra_-_Cute_Name.mp3
Paul_Oakenfold_-_10_-_State_of_Emergency_-_Banks_of_Babylon.mp3
Paul_Oakenfold_-_11_-_Juno_Reactor_-_Jungle_High.mp3
Paul_Oakenfold_-_12_-_Ennio_Morricone_-_Miscrere.mp3
Paul_Oakenfold_-_13_-_Virus_-_Moon.mp3
Paul_Oakenfold_-_14_-_Grace_-_If_I_Could_Fly.mp3
Paul_Oakenfold_-_15_-_Our_House_-_Floor_Space-retry.mp3
[02]Paul_Oakenfold_-_02_-_Ryuchi_Sakamoto_-_Merry_Christmas_Mr_L.mp3
[03] Paul_Oakenfold_-_03_-_Y-Traxx_-_Mystery_Land.mp3

[download]
Output 
Paul Oakenfold - HHC - We'Re Not Alone.Mp3
Paul Oakenfold - Red Sun - This Love.Mp3
Paul Oakenfold - Ryuchi Sakamoto - Little Budha.Mp3
Paul Oakenfold - Man With No Name - Teleport.Mp3
Paul Oakenfold - Terrorvision - Conspiracy.Mp3
Paul Oakenfold - Man With No Name - Sugar Rush - Retry.Mp3
Paul Oakenfold - Eric Serra - Cute Name.Mp3
Paul Oakenfold - State Of Emergency - Banks Of Babylon.Mp3
Paul Oakenfold - Juno Reactor - Jungle High.Mp3
Paul Oakenfold - Ennio Morricone - Miscrere.Mp3
Paul Oakenfold - Virus - Moon.Mp3
Paul Oakenfold - Grace - If I Could Fly.Mp3
Paul Oakenfold - Our House - Floor Space - Retry.Mp3
Paul Oakenfold - Ryuchi Sakamoto - Merry Christmas Mr L.Mp3
Paul Oakenfold - Y - Traxx - Mystery Land.Mp3

[download]

--perlplexer

In reply to Re: a task for a regular expression expert by perlplexer
in thread a task for a regular expression expert by emilford

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.