Notability is sourcing: Articles generally require significant coverage in reliable sources that are independent of the topic. They even made a catchy name for it: https://en.wikipedia.org/wiki/Wikipedia:The_answer_to_life,_the_universe,_and_everything (well they borrowed it but you catch my drift). Even if every single claim is Verifiable, it will be deleted if there aren't enough secondary (independent of the topic) sources because it's dangerous and likely non-neutral to only hear the subject's view of themselves. Confusing Notability with something else is a pretty common pitfall for new article creators, so there's things like "Articles for creation" where you can submit article drafts for review and have conversations with the reviewer on what exactly is wrong with your article, as well as many other guides and forums like Help:Your first article, WP:Teahouse, and WP:Help desk.

It didn't help that a couple years later somebody else decided it was notable after all and created the article.

The essay https://en.wikipedia.org/wiki/Wikipedia:Too_soon is often cited to say "This might get the needed sourcing in a few years, but right no we can't tell, so it's better to create the article again when it has what's needed to align with our content guidelines rather than rush to make a misleading one right now." So either that's exactly what your situation was, or . I'd love to take a look at the article you're talking about.