Maybe your car player uses a cache for the cover-art?
Well, it still seems not to be clear whether the resolution is the problem. There are other possible reasons, even some really absurd ones like this the user ryerman wrote of:
You have to decide for yourself which resolution suits your needs.
I don't have a car player (in fact I don't even own a car). So to me it is does not matter which resolution is sufficient for a rather small display.
I can tell you my decisions for cover-art:
Because I don't want my mp3s get too big just because of non musical content I decided to use jpgs with a resolution of 800x800, take only the front-cover to embed and a slightly higher compression. That results in pictures of about 50-150 KB size depending on the picture content.
I take pictures with the highest resolution I can find on the internet (with the software AlbumArtCover) as source and decrease the resolution to 800x800 and compress them myself. This results in better quality and smaller size than original found 800x800 pictures.
I do this because to me it makes no sense to decide to use mp3-compressed songs with about 3-8 MB size and then blow them up with nice to have but not essential cover-art to the double size with high-resolution cover-art.
But as I am centered on albums and not single songs and all my songs are in album-folders I store the high-resolution art-work as files in this folder and not only the front-cover but also additional cover-art (back-cover, booklets, CDs) as far I can find it.
So I am able to change the embedded cover-art to a higher resolution if I change my mind about the optimal resolution some time in the future.