Help

We just installed our SMTP server (Domino) and we bought a new domain and
asked for an MX record...well he have done evrything needed to have our mail
server working and we succeded...Howerver, lately we noticed that gmail ,
hotmail  yahoo and other known webmail don't receive our emails, we can
receive emails friom them but we can't send...
It's important to explain the timeline so you can understand:
First we bought a domain name : oilibya.ma
We bought a range of IP addresses 81.192.160.32 --- 81.192.160.44
we asked for an MX record entry on the DNS : 10  mail.oilibya.ma
81.192.160.35  259200
It worked juts fine...
Then our local carrier made a mitstake and put 80.192.160.35  instead of
81.192.160.35
so it was replicated on all the DNS servers and we couldn't receive emails
then we contacted them and we asked them to rechange it to
81.192.160.35...they did and we started to receive emails
but since then we couldn't send to gmail and hotmail....
so we contacted them and they said they forgot to put an entry for
rDNS....so they corrected that and I could check It's working, the reverse
resolution is effectivly done hoewever we still cannot send to gmail and
hotmail  (we receive)
I started to check the headers of the emaisl that I received when the
setting was working and I discovered the SPF...now I just wanted you to help
me out to find why gmail, hotmail and other known webmail are not receiving
our emails...is it because of the SPF...should we ask our provider to create
an SPF entry ???
I have copied and pasted below the headers that worked before to send to
gmail

   Hop
Delay from by time (UTC) 1 * NMLSERV.XX.COM  <http://casnml99.ol.com/>
81.192.160.35 mx.google.com 6/8/2008 4:28:35 PM 2 1 second  6/8/2008 4:28:36
PM 3 4 seconds  6/8/2008 4:28:40 PM
   HeaderName
 HeaderValue
 Delivered-To
 bouchaibi <at> gmail.com
 Return-Path
 <Jamil.Bouchaibi <at> oilibya.ma>
 Received-SPF
 neutral (google.com: 81.192.160.35 is neither permitted nor denied by best
guess record for domain of Jamil.Bouchaibi <at> oilibya.ma) client-ip=
81.192.160.35;
 Authentication-Results
 mx.google.com; spf=neutral (google.com: 81.192.160.35 is neither permitted
nor denied by best guess record for domain of Jamil.Bouchaibi <at> oilibya.ma)
smtp.mail=Jamil.Bouchaibi <at> oilibya.ma
 To
 bouchaibi <at> gmail.com
 MIME-Version
 1.0
 Subject
 test
 X-KeepSent
 F56E4D69:D43013F3-00257462:00608BFC; type=4; name=$KeepSent
 X-Mailer
 Lotus Notes Release 8.0.1 February 07, 2008
 From
 Jamil.Bouchaibi <at> oilibya.ma
 Message-ID
 <OFF56E4D69.D43013F3-ON00257462.00608BFC-00257462.0060D54D <at> oilibya.ma>
 Date
 Sun, 8 Jun 2008 17:37:40 +0000
 X-MIMETrack
 Serialize by Router on nmlserv/LIBYAOILMA(Release 8.0.1|February 07, 2008)
at 06/08/2008 05:37:42 PM, Serialize complete at 06/08/2008 05:37:42 PM
 Content-Type
 multipart/alternative; boundary="=_alternative 0060909100257462_="

  Hop Delay from by time (UTC) 1 * NMLSERV.XX.COM  <http://casnml99.ol.com/>
81.192.160.34 mx.google.com 6/9/2008 10:51:14 AM 2 0 seconds  6/9/2008
10:51:14 AM 3 1 second  6/9/2008 10:51:15 AM
  HeaderName HeaderValue Delivered-To bouchaibi <at> gmail.com Return-Path <
Jamil.Bouchaibi <at> oilibya.ma> Received-SPF neutral (google.com:
81.192.160.34is neither permitted nor denied by best guess record for
domain of
Jamil.Bouchaibi <at> oilibya.ma) client-ip=81.192.160.34; Authentication-Results
mx.google.com; spf=neutral (google.com: 81.192.160.34 is neither permitted
nor denied by best guess record for domain of Jamil.Bouchaibi <at> oilibya.ma)
smtp.mail= Jamil.Bouchaibi <at> oilibya.ma To bouchaibi <at> gmail.com MIME-Version
1.0 Subject test X-KeepSent 0A51E6A2:19B401A4-00257463:0040B960; X-Mailer Lotus
Notes Release 8.0.1 February 07, 2008 From Jamil.Bouchaibi <at> oilibya.ma
Message-ID <
OF0A51E6A2.19B401A4-ON00257463.0040B960-00257463.0041F2EF <at> oilibya.ma> Date Mon,
9 Jun 2008 12:00:18 +0000 X-MIMETrack Serialize by Router on
nmlserv/LIBYAOILMA(Release 8.0.1|February 07, 2008) at Content-Type
multipart/alternative;
boundary="=_alternative 0041D16500257463_="

 Thanks for your help....