Not sure about your setup, but I usually get that message when I'm sending mail for my work IMAP account when I'm not VPNed into work's network.
Sometimes, if google's IMAP server is being slow, I'll get the same message. But if I click "edit message" or whatever the don't-send-through-the-other-server option is, I just resend the message and it goes through.