Hi!
I'm sorry to report..but this problem is not an easy fix. You're going to have to set reverse dns and spf records..and go to the website and do what it says to do.

It's going to take some time and effort..just know that ahead of time.

>>>>> Set up an account on live.com for yourself..and then file a ticket with Microsoft about this. Doing this will help you speed things up a bit.

>>>As far as your other outlook problem..you need to properly setup a mail server.
The easiest way to do that is bring in a control panel that does a lot of that for you.

The harder way is to manually set it up...there are many how-to's on the web..just search for them with your OS choice.

Bryon