You're obviously attacking this problem the right way.
It's pretty clear to me that the parameters being passed to proj are not what you need. But I don't know where to go next.
I would suggest you try posting on the proj users mailing list, or reposting here with a more specific subject line ("proj parameters for Greek TM3' projection", maybe). I think that Mapscript is working fine. It's just a question of finding the right projection parameters.
Hal
