Could be several things. Try a Telnet connection to smtp.ent.lyse.net port 25 and see what response you get on your HELO and MAIL FROM entries. If it still doesn't work I guess they have a helpdesk at lyse.net that might have more information about it.
You could use MercuryC too of course, but there is probably no real advantage if you need to relay through smtp.ent.lyse.net anyway.
/Rolf