Más interesante que fijar una cantidad, es fijar una antigüedad.

Por ejemplo almacenas las notificaciones durante 1 mes... 15, 10, 7... días. Puede ser un valor dependiente de las notificaciones diarias medias que que tenga un usuario. Un usuario con muy pocas notificaciones, podría mantenérselo durante 1 mes... los usuarios con notificaciones muy activas, quizás baste mantenerlas una semana.

Lo importante es considerar que nadie tendrá interés (habitualmente) en consultar una notificación de 1 mes atrás si entre esa y la última median 5000 notificaciones, en cambio es algo tolerable para alguien que solo haya recibido 20 notificaciones en ese mes.

También puede shacerlo mixto, eliminar lo que sobrepase cierto número de notificaciones o cierta antigüedad aunque no se alcance esa cantidad.

...y preferiblemente a eliminar solo una, borra la mitad más vieja cada vez. Si solo borras una cuando esté la bandeja llena, tendrás que constantemente se estarán borrando notificaciones, si hay mucha actividad, la base de datos no tendrá 'descanso'.

Con algo de prueba y error, acabarás encontrando un punto que puedas considerar acertado...