I unlocked the ultimate recipes but when I started another ng, they all disappeared. Am I suppose to redo all of the quests + get the 500 kills all over again to be able to access the recipes? I did choose the option to keep previously learned recipes.

You need to complete Quest 148 - Training (the Wil 500 kill one) on every Playthrough.
The Ultimate Recipe is a Key item.
Key Items do not get carried over on new games. (like the Bronze/Silver/Gold keys).