I have spent a long time going their site, answering questions on forms to finally bring me to the following URL:
Fill this form out, and within about a week, your email should start delivering to gmail accounts again. Typically Google will not write you back, they will just lift the block.
Before you fill in the form, make sure that your server is no longer sending out spam. Otherwise, they will either reject you, or blacklist you again right away.