Yes, unfortunately, with shared hosting one abusive account can ruin it for everyone else on the same server. However, eUKhost is very good at tracking down and suspending or removing abusive accounts so I am sure that the account that was causing those problems is no longer on the server. However, due to AOLs block, eUKhost will have to request that the server is unblacklisted but the information in the error message posted above seems to imply that AOL are very happy to discuss unblocking in legitimate circumstances - which this is
