This happens to me as well from time to time, the cause is melpa keeps only latest version of packages, so it is safe to always update package archive with
M-x package-refresh-contents or
M-x list-packages before installing package from melpa, of course, this is time-consuming and inconvenient.
Here is a rough programmatic solution that I can think of at this moment, I guess both
M-x package-install some-package and
(use-package some-package :ensure t) should work even when
some-package's archive is outdated.
(defun package-install-ensure-melpa (orig-fun &rest args)
(apply orig-fun args)
(apply orig-fun args)))))
(advice-add 'package-install :around #'package-install-ensure-melpa)