Is it possible restrict access to specific customers only (not based on subsidiary but based on customer category)? I was able to create a workflow with Return User Error to prevent them from viewing/editing certain customer records. But obviously they can still run a saved search or report to extract the details of those customers. Is this even possible?

You could try creating a custom segment and then setting up a Role to restrict based on that segment. Hard part is the data management side to ensure all of your records have that segment kept up to date. You'd also want to test extensively to make sure it doesn't introduce any unintended consequences, like locking out record types you don't want locked out. But it may get you where you want to go.

I dont think you can use custom segments for restrictions on roles. Unless its changed recently

Yeah, custom segments can't be used as a restriction on roles.

Argh, frustrating. Yup, my mistake. Cannot select custom segments to restrict roles. I guess that means you could set up specific Departments or Classes for the customers and restrict on those.