Non ne sto cavando le gambe...

Questo

codice:
/<span style=\"text-decoration: underline;\">((?!<span))<\/span>/si
Non trova niente.

Quest'altro

codice:
/<span style=\"text-decoration: underline;\">(.*(?!<span).*)<\/span>/si
trova, ma ignora il fatto che dentro al tag ci sia la stringa "<span"

Forse le espressioni regolari non sono abbastanza potenti per quello che vorrei fare io