@michael_m Seems like you have a number of options.
Can you categorize the jobs into more specific types (e.g. region, job type, etc.) and then add them to more category-specific "job board" pages? Even if you had duplication across job boards, seems like you'd get better crawl + indexation coverage. Anything to create a more clear crawling path to those pages. Even 20-50 job categories (or other sort/filter features) might provide benefit, and those category pages probably have a better chance of ranking on their own.
Cross-linking from similar/related jobs might also be a good option to explore. Much how we link to related questions here in the Q&A.
Orphaned pages aren't always a problem, as long as the pages are getting indexed and ranked. I imagine the search volume is pretty low for some of those jobs, but Google's sitemap indexation report is going to be your friend here.
Hope that helps!
Are the job postings covered in a sitemap? As SEO tools are finding them as orphaned, I assume they are discovering the pages via sitemaps.