In my experience, the chance of a mob dropping a head is significantly increased by the quality of the tool you use.
When you get your mits on a star metal cleaver (perhaps modded for tool efficiency too), you’ll get a head more often than not, so it’s arguably a progression issue.
That some mobs don’t have a head in their drop table is perhaps a design choice, but since they weren’t promised, I don’t personally have a problem with that.
If it’s not listed in the taxidermy feats page, I wouldn’t expect one.
I was disappointed when I didn’t get one from my first boss kill too, but you’ll be drowning in them soon enough.
Fwiw, the gorilla type rocknoses drop a rock nose king head which can be used to complete the boss head journey step. That might be a bug tho, but it’s a fairly easy way to complete it. I think someone can just trade you one of theirs to the same effect too.