Bash / Sed, <strike>705</strike> <strike>650</strike> <strike>588</strike> 583 chars
----
**Logic**: Basically, simply using `sed` to replace repeated parts of the text. This song has lots of them.<br>
But `sed` commands, like `s/X/something/` tend to be repetitive, so I decided to use `sed` to shorten it.<br>
So I feed `sed` with lines in the format `Xsomething` and it builds `s/X/something/g` from this. These commands are fed to `sed` again, to edit the song.<br>
With this approach, the cost of a translation is very small, so I can use lots of them and remove almost all repetition from the text.<br>

    sed "`sed 's#.#s/&/#;s#$#/g;#'<<Q
    LMWe'veKn each o!r for-o longPr hearHzchJbutP're2o-hy2-@Insidexe bothKxhaHCJonMWeK ! game+we'reZpl@
    TMI justxanna _UFGotta QuXerstaXR
    RM~Squp~letqdown~runzrouX+desertU~Qcry~sayCodbye~_z lie+hurtU
    E(Ooh)~S, neverZSM(GV
    F how=feelingM
    Ht's been
    %(Ooh, gV
    Vivequp)M
    ~MNeverZ
    K know
    @ay itM
    Qmakeq
    qU 
    U you
    PMYou
    = I'm 
    +zX 
    ZCnna 
    Sgive
    _tell
    C go
    2 to
    !the
    Jing 
    Xnd
    z a
    x w
    - s
    M\n`"<<_
    We're no-trangers2 lovePK ! rules+so do I
    A full commitment'sxhat=thinkJofPxouldn't get this fromzny o!r guyT
    LAX ifqask meFDon't _ meU're2o bliX2-eeRRMM%%EELTRR

Notes:<br>
The decompression engine is just 41 characters long. The other 547 are the translation table and compressed text. `bzip2` compresses the song to 500 bytes (without the engine, of course), so there must be room for improvement (though I don't see how I'd add Huffman encoding or something like this cheap enough).<br>
`<<Q` (or `<<_`) is used to read until a given character. But the end of script (or backquote expression) is good enough.


Older and simpler solution, 666 chars:

    sed "
    s/L/ MWe'veKn each other for so longMYour heart's been aching butMYou're too shy to say itMInside we bothK what's been going onMWeK the game+we'reZplay itM/;
    s/T/MI just wanna tellU how I'm feelingMGotta makeU understandR/;
    s/R/M ~giveU up~letU down~run around+desertU~makeU cry~say goodbye~tell a lie+hurtU/g;
    s/E/(Ooh)~give, neverZgiveM(GV/g;
    s/V/iveU up)M/g;
    s/U/ you/g;
    s/+/ and /g;
    s/K/ know/g;
    s/~/MNeverZ/g;
    s/Z/ gonna /g;
    s/M/\n/g
    "<<Q
    We're no strangers to love
    YouK the rules+so do I
    A full commitment's what I'm thinking of
    You wouldn't get this from any other guyT
    LAnd ifU ask me how I'm feeling
    Don't tell meU're too blind to seeRRM M(Ooh, gV(Ooh, gVEEL TRR


  [1]: http://www.youtube.com/watch?v=dQw4w9WgXcQ