Re: Wrong priority
Now that we're out of virgin IPv4 space, anyone running a mail server should check to ensure that those IPs aren't on any of the major RBLs.
I had the same issue a few months back where my ISP allocated us a new /24 but it was black-listed, took a few emails to Spamhaus and a few others, but got everything cleared up. Doing this has more or less become a necessity in this day and age. Hell, you should be doing this periodically on blocks you already own.