En cada boletin que envias por correo electronico poner al final un enlace tipo
Si no desea recibir mas correos pinche aquí: www.tupagina.com/
[email protected]&id=id_ de_correo_en_bd
Y ese enlace que haga una sentencia mysql que borre la entradadonde coincide tanto correo como id, así no teiens a nadie que te vaya borrando correos, luego mostrar un html en el que se confirma que el correo fue eliminado de las bases de datos.
Es una idea..