When you say it is not “searchable”, do you mean you can’t find it in the Search UI? How long between when you created the access profile and when you tried to search for it? There is a latency in search because objects have to be loaded into the search database before they can be found. The time this takes can depend on system load.
I have noticed this same behaviour, but I think all you need to do is wait. I have tried calling the API for access-profiles in v2, v3 and BETA and usually the (new) access profile is missing from one of these requests which I find quite odd. I would think they all call the same db?