The easiest thing is to add any premium plugins (ones not available via wpackagist or Github) to your project’s version control. Yes you’re adding third party code to your project, but in this instance at least you’re not reinstalling plugins every deploy. That sounds horrible.
Your other options are to set up each plugin in it’s own Git repository, you could do this on Github or Bitbucket, and add a valid composer.json to each plugin, that would allow you to pull in those plugins to multiple projects. But then you’re stuck updating them manually via Git after every update.
You can also look into creating your own Packagist service with Satis (free) or Toran (paid service). This would give the most Packagist like experience.
edit: btw, this has been discussed quite a few times before:
How are you searching WPackagist? I’ve noticed that searching by plugin name doesn’t yield that many results. When you search for the plugin’s package name, which is how the zipped file is called in the WordPress plugin directory, I’m able to find most, if not all, plugins.
So you might want to try “my-wordpress-plugin” instead of “My WordPress Plugin”.
I have worked on sites where we have a Toran server and we garden the paid plugins in their own gitlab repos and such. I have also worked on sites where we just check the paid plugins into git. Both methods work great.