https://market.android.com/details?id=com.birbeck.android.coverart
結局うまくアルバムアートを付加できなかったものは、
android上でCover Art Downloaderを用いて追加することにした。
サーチ機能も結構な精度だし、アルバムアートをアンドロイド上のファイルから指定することもできる。（ただし勝手にトリミングされる。）
サーチに引っかからなかったアルバムだけ
Dropbox経由でandroidに落としこんで登録することでアルバムアートをうまいこと同期できない問題は解決した。
ホントはこんな面倒なくても同期できるのが一番なのだが。まぁ、解決策があるだけマシかな。
