Windows Media Playerでは、特定の領域にアルバムアートのキャッシュを保存しています。また、フォルダーにも縮小表示のキャッシュが存在します。これらによりファイルのアルバムアートを削除してもキャッシュによりアルバムアートが存在するかのように表示される場合があります。
キャッシュを削除せずにファイルのアルバムアートが削除された確認するには、他のパソコンまたはスマートホーン等で閲覧するか、違うフォルダーにコピーしてみると確認できます。
WMAファイルを移動させずにキャッシュを消すには次の手段を順番に試して行きます。

実行環境

Windows 7 Enterprise Service Pack 1 64bit
Windows Media Player 12.0.7601.18150

エクスプローラーでALT+T O 表示タブで詳細設定の隠しファイルを表示するにチェックを入れる

Windows Media Playerでは、ライブラリに取り込まれたWMAファイルのアルバムアートはキャッシュされます。 キャッシュにより、WMAファイルのアルバムアートを削除したり変更してもWindows Media Playerで再生時に反映されないことがあります。この場合、一度アルバムから該当WMAファイルを削除し、キャッシュを削除すれば、WMAファイルのアルバムアートが優先されます。（縮小表示用のフォルダー内に作成されるキャッシュが邪魔をする場合があります。）

ライブラリからWMAファイルを削除する

Windows Media Playerを起動し、該当のアルバム上で右クリックをし、表示されるメニューの削除を選びライブラリからのみ削除するを選択すれば、アルバムから削除されます。

アルバムアートのキャッシュを削除する。

ライブラリに取り込まれたWMAファイルのアルバムアートは次のフォルダーに保存されています。隠しファイルを表示する状態にして次のフォルダーを開き、フォルダー内のファイルを削除します。次のユーザー名はログインしたユーザー名に置き換えてください。
C:\Users\ユーザー名\AppData\Local\Microsoft\Media Player\アート キャッシュ\LocalMLS

該当WMAファイルが存在するフォルダーに作成されるJpegファイル

フォルダー内に隠しフォルダーで AlbumArt_{～}_Large.jpgやAlbumArt_{～}_Small.jpgやAlbumArtSmall.jpgが作成されることがあります。これも削除しましょう。

Thumbs.db

画像ファイルや動画、音楽ファイルがフォルダーに含まれるとThumbs.dbという隠しファイルが作成されます。
Windows 7では作成を抑制するオプションは内容です。
これを削除するには、Thumbs.dbファイル自身を削除してみる、それで状況が変わらなければ、ドライブのプロパティでディスクのクリーンアップを実行すると消えます。