The bug
The more workstations (points of interest / POIs / job site blocks / job sites) are near a villager, the longer it will take it to get a job. This also is the case if the villager cannot pathfind to most of the nearby POIs.
To reproduce
Spawn a villager in an enclosed space
Place a lectern near the villager
→ ✔ The villager immediately gets the jobBreak the lectern
Go outside of the enclosed space
Run
/fill ~ ~ ~ ~15 ~15 ~15 minecraft:smithing_table
Place a lectern near the villager
→ ❌ The villager takes ages to get a jobRemove all the smithing tables again
→ ✔ Now the villager immediately got a job again
Video
Linked issues
Comments 10

Unable to reproduce in 1.16-pre2. Villager gets the job almost immediately, regardless of whether there are smithing tables nearby or not.

Im able to reproduce the bug, if you have 40 Lecterns in your villager trading hall, no matter how close the new lectern is, the villager will take several time to take it.
Video Prof: https://youtu.be/u8fj8o6STl8
Was able to reproduce this in 1.16-pre5. Make sure the villager cannot pathfind to the large amount of workstations placed nearby.
Fixed in 1.16.2-pre1 🎉

Tested and fixed! A bit sad that if they aren't in a enclosed space still takes ages to get a job, at least is a fix for enclosed spaces!

I am experiencing this problem. Doesn't appear to be fixed.

This issue seems to be back in 1.16.5
If you think you have this or a similar issue, please file a new bug report.

It is not fixed for me
This might just be speculation, but as far as I know, POIs are added to a list when they are placed. When a villager searches for a job, it probably goes through that list one by one. Now, the existance of this bug would probably be caused by the fact that newly placed POIs are appended to this list. If they would be prepended instead, this issue would not be as severe.