I have built a tool that uses Property-based testing to generate tests for an API given, e.g., an OpenAPI specification. I published an article of how I was able to discover bugs in a released version of GitLab CE: How to create 1040 tests targeting Gitlab in 5 minutes with Humlix
Somehow GitLab let these bugs slip through to production, which shows how hard it is to find bugs that require out of the box thinking for the input data.
Implementing Property-based testing code can be challenging and leaves you with more testing code to maintain.
It would be interesting to hear your thoughts on using a tool like Humlix to generate tests for your REST APIs.