It's not necessarily hard, but you'd have to have a solid plan, and it will take you probably at least 8-10+ generations (which is at least 8 years) to breed back to type, and if you were to do it you'd have to have several lines going to avoid too much inbreeding. I wouldn't recommend trying to make them from scratch as it'll take you a long time to get good birds again. I'd recommend buying eggs or birds from someone who already has them, it will save you a lot of time and money.
Keep in mind that whatever breed you use to introduce the barring gene, you'll have to breed out all of their traits that don't conform to the standard for Phoenix, while also breeding back to Phoenix traits. It might not be hard, but it would take a lot of time and dedication on your part.
And you are right that an outcross was done to achieve the barring in Phoenix, it was with genetic hackle birds (which are arguably harder to find than actual Barred Phoenix).