My idea is using existing seed, but generate as many address as possible until you find address that match you need.
BIP-85 seems more suitable here.
User can deterministically generate the starting key (step 1 outlined
here) at a predefined standard path (
m/83696968'/app_no'/index') and finds the vanity address that way.
This avoids any overhead of having any extra steps while adds the possibility of recovering the key from the seed backup by taking the same (time consuming) steps.