What outgoing (SMTP) server do you have set-up for Gmail in OE? I use smtp.gmail.com (not my ISP's SMTP server)
Unlike many other mail accounts, you can send through gmail servers even if you're broadband connection isn't Google (it wouldn't be, would it). Contrast this with sending a mail from a tiscali address using PlusNet as ISP - one would have to use the PlusNet SMTP server.
Now, having said that, I can't say that this has anything to do with your prob. But you never know.