Don't have a definite solve, but did some research you might find helpful.
It looks like Fossify Contacts (and most privacy respecting contact apps) maintain a separate database of contacts from your phone's "true" contact database. This means the app occasionally needs to sync up with that "true" database.
My research seems to be pointing to GrapheneOS as a whole having a ~~current~~ recent issue with syncing that "true" database with a bunch of apps. This Github Issue appears to have resolved it (though I didn't read all of the comments on it), so unclear what else needs to be done.
I finally got Android Auto setup on my phone yesterday (it was a RTFM issue), so your post caught my eye. I don't see myself having time to do a lot of testing to support finding your fix, but I'mma try this with a couple of contacts apps over the next day or so and see if it isn't just a "use a different app" solution.
In the mean time, hope you have good luck finding a solve!
Edit: My Clanker Assistant suggested this:
Add your Google account if not already done:
- Go to Settings > Passwords & accounts > Add account > Google
- Sign in (this uses GrapheneOS's sandboxed Play services, so it's contained).
- Enable sync for Contacts.