Victory medal was first released in Japan in 2005 Victory Medal (Battle Road promo) - Bulbapedia, the community-driven Pokémon encyclopedia
Victory medal was also legal in the japanese legacy format but tcgone chooses to use tpci cardpools over the japanese ones for things like standard so I don’t know if that omission is intentional.