You mention its not an open relay and yet its accepting email from random addresses for delivery ? if your adding IP's to a deny list and thats blocking it does suggest its a relay. Are their any odd entries on the Allow list ? and are you 100% sure its not setup to allow relaying ?