This is actually a pretty common issue. Non-embedded album art is not included in your iTunes library file size estimate number. You can have iTunes look up the art work for one file and its size will not increase. Copy that over to an iDevice and iTunes will report a larger file. Now, there is some debate as to whether non-embedded art is stored with the music or in the Other category. Given my experience, I would say it can be a mixture of both. For example, I copied an album over to my 4G iPod touch. It was 86.5 MB in size yet the amount of music I had increased by 88 MB. The album art that iTunes downloaded was 1.5 MB in size. The size of my Other data did not increase at all. From this syncing operation. However, my Other data is about 920MB which signifies that something is going on, I just don't know what.
There was a discussion about this over in the iPod touch section of the forums as others were experiencing the same thing. Either way, it sounds like the issue is bigger with iOS4.x vs older versions of it (though I had the same problem with my 120GB iPod classic).
Well, I did some research using iPhoneBrowser to peek into the file structre, and the discrepancy is because of the artwork thumbnails - ITHMB files.
Is there any way to avoid these files being created, perhaps by embedding the artwork directly into the MP3 files rather than having iTunes store it in its database? I'd really love to reclaim my 900 MB of storage; I only have 16GB and I'm running out of space!