So, I've now simply moved my email validation to an external server, which I query via XML-RPC. It then performs the email validation - and since it runs on a static IP, it's also accepted by AOL.
Anyone who wants to play around with this, the service is accessible via SOAP or XMLRPC. The address for XMLRPC: http://simon.bofh.ms:1111/RPC2 and then call the method mailcheck.validateEmail(adr) there. The address for SOAP: http://simon.bofh.ms:1111/SOAP/mailcheck and then call validateEmail(adr) there. Documentation of the method for this module can be found at http://simon.bofh.ms:1111/API/mailcheck. A WSDL for .NET people and others who need that sort of thing can be found at http://simon.bofh.ms:1111/WSDL/mailcheck. By the way, the web service was created using TooFPy. The corresponding tool is included in the source package - or can be viewed directly in CVS.