Well if you sync with iTunes you won't be able to use the file-browser because of how iTunes obfuscates all the file and directory names (apparently, and it might have been someone on this very forum who pointed this out to me, it does that in order to minimise the memory the ipod OF needs to use for its own database, and, not, as was my first guess, for some sort of misguided DRM copy-protection nonsense). Hence those 'random strings'.
Personally I'd just give up on using iTunes, but if you insist on being able to use the OF on the iPod, then you have to make sure all the tags are filled in correctly so the database can handle them. I can only guess that when you down-convert them using iTunes during sync, it doesn't retain the tags from the original ALAC files (assuming they have them) for the downsampled versions. Ipod OF presumably doesn't use those tags, it uses it's own database instead, so I'm guessing iTunes doesn't bother to retain them during the conversion process.
Either convert all the files beforehand on your computer, then use some utility to fill in all the tags again, or maybe use some other utility to do the conversion that retains the tags?
Edit - might be worth looking at the converted files on the ipod with something like mp3tag, just to see if the problem is indeed that the tags are not being copied during the conversion/sync process.