Buenas:
Este tipo de publicidad intrusiva suele estar dentro de apps de terceros, generalmente de origen dudoso, como puede ser cualquier tipo de app de pago descargada fuera de la play store. Tambien es posible que venga en archivos descargados de internet, ya sea apk como ya he mencionado, o incluso fotos, videos etc...
Revisa de nuevo las apps que tienes instaladas, sobre todo las mas recientes, a veces la publicidad de estas no se manifiesta de forma directa, asi no sabes a que app pertenece y no lo erradicas a la primera de cambio.
Si aun asi no encuentras la manera de solucionarlo pasate por
aqui y metele la rom limpia, de esta manera si o si se solucionara.
Saludos