Paprika and tumeric fade quite quickly for me when infused, but paprika added to the lye or at trace seems to hold up better. Someone on here told me tumeric held its color better when the powder was added straight to the batter vs. infused, but I haven't tried that yet.
I have tried curry powder added at trace, but was a bit underwhelmed by the color.
For yellow/orange, annatto infusion and freshly grated orange peel work well for me and the color sticks (there's only one batch of annatto that faded a bit after a year and there's a slight amount of browning of the orange peel soap after +- 3 years).
I've recently tried tomato puree which turned a lovely peachy pink color, but can't say if it'll last.
Green colorants tend to fade to brown when the colorant is added straight to the batter or lye water. Matcha only gives green when infused in oil, otherwise it'll turn brown.
In terms of natural greens, spirulina added at trace or to lye water holds up the best for me (it's possible to infuse, but the color will be a lot lighter and might take a week to show). Adding sugar and salt to the soap while keeping the temps low seems to help prevent fading of spirulina soap, although keeping the soap away from light is the most important way to protect the color of your naturally colored (green) soap.
I also had quite a bit of luck with freshly pureed, frozen pandan leaves blended in at trace. The color is sticking around for almost a year now. I tried to redo this with frozen spinach, but the soap smelled a bit weird.
Most natural reds/purples (like fruits and berries) aren't pH stable and turn brown in soap. A lot of people on here have had success with madder (or manjistha) root powder. Clays also work well.
Alkanet infusion works for most people to produce a purple soap, but alkanet powder added straight to soap batter will turn brown.
For blue, indigo extract works well when added to the batter or lye water, but be sure to read the label so you know what species of indigo you have, some are more greyish blue (I use indigofera tinctoria, which is denim blue)
Like some others, I have good experiences with cocoa powder, but a small piece of melted dark chocolate also works to color soap chocolate brown.
Activated charcoal works well for grey and black.
Hope this helps!