I had the same problem with a O2 mail account on blueyonder broadband. O2 said it was because their mail address had to be the default for sending & receiving and not a second address. I didnt get the same problem using onetel as a second adress.
Might be worth checking if tiscali is the same. Not exactly a solution, more a workaround but might sort it.