I have a membership signup system, where users are asked to verify their e-mail address. The problem is that email sent is in hotmail rerouted to the junk mail.

This might be because I am runing a VPS and have mysite.com hosted on myhost.com, where myhost.com is the VPS domain.

I actually want mysite@mysite.com to be the return address, but I also tried setting it to mysite@myhost.com, since the smtp server is host.myhost.com.

Can anyone help?

hotmail uses a number of factors to determine junk mail. Anything from a domain it doesn't recognize, combined with 1 or 2 other factors that it wouldn't normally consider a red flag, will cause your email to be treated as junk.

Though this may not solve your problem, it will increase the odds of getting your mail into the inbox. Have the server send you some emails at a hotmail address. Go into your junk folder, open each email, and tell hotmail that they are not spam.

This will help significantly. It wouldn't hurt to make sure your zone file includes a ptr record as well.