英語ですが参考になりそうな情報を見つけました。
askubuntu.com

iyhoovip による投稿:

Amazonで買ったMP3はアルバムアートがあるのです
アルバムアートを追加したいのではなく正しいのを表示したいのです
キャッシュされたというのはAmazonではなくローカルのVLCの話です
先行配信云々ではないAmazonで買ったMP3はVLCでファイルのサムネイル通りのアルバムアートが表示されます

vlc に詳しいわけではありませんので、当てずっぽうですが....

ファイルブラウザで、ホームディレクトリを開き
Ctrl-h を押し、ドットファイルを表示します
そこに
.catche
.config
.local
などのディレクトリが表示されます。
その中に、vlc ディレクトリがありますので、
中のそれらしいものを探してみては？

VLCはUbuntuソフトウェアセンターからインストールしたと思いますが隠しファイルを表示して下記のフォルダにアルバムアートのキャッシュがフォルダ名別にあったので削除したら解決しました
/home/ユーザー名/snap/vlc/common/.cache/vlc/art/artistalbum/