Forgot to mention that this problem occurs even without use-package usage.
The problem still persists even with the following init file:

;; Begin
(package-initialize)
(add-to-list 'package-archives
             '("melpa" . "https://melpa.org/packages/"))

(defun require-package (package)
  "Ensures that PACKAGE is installed."
  (unless (or (package-installed-p package)
              (require package nil 'noerror))
    (unless (assoc package package-archive-contents)
      (package-refresh-contents))
    (package-install package)))

(require-package 'slime)

(setq custom-file (locate-user-emacs-file "custom.el"))
(load custom-file 'noerror)
;; End