1) Settings > Add Account > Microsoft Exchange
2) Fill in the following fields:
Username: firstname.lastname@example.org (NOT your username)
3) Click 'Next' on top right hand corner
4) For the field
Use SSL: On
5) I left the rest as it is.
So now I am able to check all my emails!
PS: Apparently there were 2 other methods before when Microsoft didn't allow Hotmail on iPhone4: the Izymail method and the POP3 method. You can try them if this does not work out for you.