In older versions, fruit trees never flowered or produced fruit in their first year.
1.22 was supposed to fix this, though. "Fixed: Wild fruit trees not fruiting in the first year", says the changelog. That unfortunately doesn't give us much to work with. We don't know what was 'broken', and we don't know what the fix was.
One thing to keep in mind, however, is that berry bushes aren't seasonal. They cycle through flowering and fruiting on a timer that keeps running as long as the ambient temperature is high enough. That means their state can be effortlessly randomized at world start.
Fruit trees, on the other hand, are very much seasonal. They flower exactly once a year, during a specific window of time. For the vernalizing trees, that is after they come out of winter dormancy, so usually sometime in April. For the southern evergreens, it's a range from February to April, except for oranges.
The game starts on May 1st. And time before that date is not simulated.
Because you need a fruiting stage to produce a harvest, and you need a flowering stage to enter a fruiting stage, it's possible that a tree that didn't get a chance to flower because April didn't exist, will skip its entire cycle for the first year.
Meanwhile, orange trees start flowering in June. So those should be absolutely fine, and that sort of lines up with your observation of southern trees that bloom in year 1. They are the only ones to bloom that late, though.
All of this is based on my speculation, mind you. I'm trying to think up a best guess as to why it isn't working. That doesn't mean that what I thought up is actually correct.