Non è che se formatti il sistema perdi la licenza. Puoi benissimo installare xp e linux, e poi reinstallare vista in un secondo momento.
La scelta va a te, logicamente con 3 sistemi operativi avrai bisogno di 3 partizioni, quindi lo spazio va progettato meglio. Ah qualsiasi sia la tua decisione, installa sempre prima windows, poi installa linux.
Se li tieni tutti e tre la sequenza è vista->xp->linux

Edit: prima di installare xp, cosa importantissima, controlla se sono disponibili i driver per quel tipo di notebook.