It is possible that Windows Media Player could take a while to find the corresponding album art. In case that this never happens you can try to use the built-in wizard. In order to do that, just right click on an album art and select Find album info. If most of the album information is correct, the wizard usually finds an exact match with the missing information. To end the process, you need to click finish and the album tags as well as the art will be updated with what the wizard found.
For more information about this problem, you can visit the following official web page.