This looks great, thanks for doing this!

... when this PR is approved as being in roughly the right direction ...

Yup this looks like the right direction. I left a few minor nitpicks, my only real feedback is that we shouldn't reuse the AutocompleteRequest for the ListPackageVersionsAsync method as they have separate request parameters.

Please let me know if you have any questions with the Azure Search implementation! This may be a good opportunity for me to beef up our developer docs 😊

Does not allow version search support for Azure yet...

By the way, I think it'd be fine for this pull request to support just the database. We can add Azure Search support later in a separate pull request.

We can add Azure Search support later in a separate pull request.

Good idea, I've made a few more little changes and it passes the tests so if we get this in I can revisit for the Azure stuff, after we've written some integration tests for it.

Thanks for your contribution!