I've been playing with this a lot more, and I think I've spotted the problem.

The media player only seems to extract the artwork when you browse the album view, but not when you just play songs. When you browse the album view, it extracts the covers and saves them in the ".mediaartlocal" directories. It also doesn't seem too good at updating them when they've changed.