I always that that the if I unchecked Include In Global Search this would make records from this custom record to not be searchable in the main search bar. Is this not the case?

That’s my understanding. If it’s still showing, maybe the desired record has a field on it that has Global Search enabled, causing it to appear.

I had at least a few record types with that box checked suddenly start getting included in global searches despite nothing changing on the setting. I filed a case and was given a defect (

Defect 599346: Custom Record > Global search returning results for records that shouldn't be included in global search

) but that was a full year ago and I've heard nothing since then. Couldn't hurt contacting support though in case more people being affected by the defect increases the priority.