This exact same thing happened to me with a client project I was working on - my client was paying $50/month for dynos, but we received no notifications about needing to pay for the database to avoid it being nuked!

On the upside, when I reached out to Heroku, they did offer to recover the database for me - but by this point in time, I'd already moved on with setting up a new one from scratch (with some changes from the original), so this wasn't particularly helpful.