So I hooked up another battery in series and, what do you know, it works every time.
Whilst I didn't check to see what the battery voltage was when this was happening, hooking up another AA in series fixed this issue for me as well, until the batteries were drained enough to start sagging again... My electronics theory is a little shot but would this be as simple as adding another capacitor to try and negate the sag in voltage? It only happens for a few seconds but the iPod refuses to recognise it after that. Re-plugging doesn't help as the sag happens again. It appears to be an issue with the batteries used, at least from my testing.
I tried cheap and midrange batteries and when I get my hands on some high end lithium "for high powered devices" types, I'll let you guys know. I have a suspicion that cheaper batteries aren't able to keep up with the demands of the iPod which may be causing a lot of these issues. If I get my hands on some Sony Eneloops as well, I'll try 'em.
This problem was occurring with my iPod 3rd Generation (MC008ZP). On a happy note, the Minty Boost v3.0 appears to work perfectly with my Huawei IDEOS U8150 phone, an Android 2.2 device (something that could be added to the compatibility list). I don't have access to an Altoids tin in Australia (nor could I afford it at the time of purchasing the kit, go figure...), but there is an Australian mint that comes in a metal container as well, called Eclipse by Wrigley. It fits the Minty Boost v3.0 almost perfectly (with a bit of lateral thinking, of course) but is a little bit tight. I'll also report back my findings with that (inc. pictures of the build) when I finish all of my damn assignment work.

The real test for this will be 2x nine hour train/bus trips two and from Sydney next week! I just hope Minty Boost, many episodes of The Big Bang Theory, Burn Notice and mobile data can save me!