I'm wondering whether Salesforce supports this at all in Omni-Channel. The use case is for teams of agents to segment their teams into groups that either accept new cases/chats, or just existing cases and updates to those. So one group would be routed existing cases (Cases where there's a response from the customer) but another team would handle new cases coming in. Is there a way to achieve this using Omni-Channel and routing configurations? would we have to create an Omni-Channel flow that creates agentWork records seperately for agents based on their Presence Configuration?
unofficialsf has a walkthrough of creating an omni flow that seems to apply to your situation. It'd come with the necessary actions to route the work.
The important point they show, is that an Omni Flow can be called as a sub-flow from a record-triggered flow. This would allow you to trigger based on your situation - a record is created or updated.
For real-time channels like Chat, Messaging, or Voice you can define the Omni Flow to run from their setup screens.
For other objects like Cases, Leads, or Custom-objects though you can invoke routing at any point, so here we’ll just use a trigger flow to kick it off whenever the case is created. Alternatively you might build a screen flow for transfer, or another record triggered flow to route whenever a customer re-opens the case. The world is your oyster.
This is also covered in the help docs Invoke an Omni-Channel Flow to Route Non-Real-Time Objects which also contains sub-docs to explain how an Omni Flow works.