We have the exact same problem with visual interfaces, and the combination of manual testing for major changes + deterministic UI testing works pretty well.

Actually it could be even easier to write tests for the screen reader workflow, since the interactions are all text I/O and pushing keys.