Hi,
Yes its true sending mail by smtp does not work in Medium Trust, a quick google of "medium trust smtp" confirms this problem. Rick Strahl has a discussion of it here.
My understanding is that most good hosting providers make it possible to relay mail through their own mail servers, so if you are using smtp credentials and server provided by them it should work whereas if relaying through something like yahoo mail will not.
In any case its an issue you'll have to take up with your host to solve it. I cannot change the fact that smtp doesn't work in Medium Trust. Good hosting companies will usually tweak their policy files to allow this in medium trust to meet their customer needs.
Hope it helps,
Joe