"According to the Apple technical support employee I just spoke with, this is a known issue for an iPod touch set to manually manage music."
Apple has acknowledged this issue, but has not provided a timeline for a fix.
The official workaround (again from my post above from Nov 7, 2008):
"I was told this was a known issue, and that the fix is to first try to reset all settings (on the iPod via Settings > General > Reset All Settings), and if that does not work do a complete restore of the iPod (in iTunes computer application)."
There is no known fix for this problem other than to perform a complete restore of the iPod. Since this is a destructive move and wipes all song metadata, it is definitely not an acceptable fix.
Apple needs to fix this critical issue.
Reliable music playback is the primary purpose of an iPod.
If you are experiencing this issue, please contact Apple technical support, let them know this is a serious issue, and report their response back on this thread. I plan on asking them once more again the status of this issue when I have some free time later this week.
And yes, I continue to experience this hideous bug every day, every time I listen to my iPod.