If your MTA is Exim (CPanel), you *might* getting a false positive from the MXToolBox diagnostic. I went to the CPanel forums and asked other Exim users to try the MXToolBox diagnostic and I have received feedback that others get this "You may have an open relay" message as well. However, if you try to actually relay a message, Exim will properly issue an error message and dump the connection. CPanel makes it very difficult to configure Exim as an open relay. Unfortunately, I have run into people who use the MXToolbox diagnostic to create their own gray/blacklist. :-(
Mark