Es que nunca te va a funcionar porque no importa donde lo utilizes mientras haya un header() no te lo va a mostrar nunca, lo que podes hacer es hacer el redireccionamiento en javascript en vez del header(), seria algo asi: (quitando el header() obviamente)
Código PHP:
Ver originalecho "<script languaje='javascript'>alert('Registro Exitoso'); location.href = 'bienvenido.php';</script>";