Can you send messages directly from the same machine (i.e., not using the gmail website or any other webmail host) and have it go through OK?

Pretty much the only time I see anything sent by my Perl flagged as spam is when I'm testing the code on my home workstation, which connects to the internet on an IP address from my ISP's dynamic address pool. Many mail servers are set up to notice that the mail is coming directly from a dynamic IP address rather than going through a "reputable" server and are more inclined to consider it spam as a result. Sending from a static IP address with reverse DNS set up correctly (or using your ISP's outgoing mail server as a relay/"smarthost" if you're not in a position to set up such a server yourself) tends to make that problem go away.