Partendo dal boot da cd di Win95 se ti dice che non trova il SO probabilmente non e' possibile fare il boot da cd (non so come funzionava il vecchio W95!). Le altre volte che hai installato W95 avevi fatto il boot da cd o no??
Riguardo al boot da floppy mi sembra strano ti dica di togliere tutto dalle unita' rimovibili! Hai detto di aver fatto la formattazione dal cd di XP, che tipo di formattazione hai fatto (il file system NTFS non lo vede il dos!)?