Sitting back and thinking about the problem I think I've identified my issue. I'm using Serban Ghita's Mobile Detection function, which is very up-to-date and all encompassing.
The mobile detection within WP Super Cache isn't as complete as my separate mobile detection library is so when a mobile user comes along that WP Super Cache doesn't ID as a mobile user it goes to cache a desktop version of the page, but my theme identifies that user as a mobile user and WP Super Cache then caches the mobile version of the page as if it were the desktop version. As far as it knows that user was a desktop user.
For the time being I removed the mobile detection function I was using within my theme and replaced it with the detection function that is used in WordPress Mobile Edition since WP Super Cache is using an identical scheme to identify, build and serve cached files.
The function within your theme that handles theme switching to desktop (if that's what you're using - it's how I'm accomplishing this) should match WP Super Cache's for the best behavior possible. You can see the function I'm using at http://pastie.org/6098853
Just change INSERT_YOUR_THEME_NAME_HERE to the name of your mobile-specific theme.
This is just a fix for the time being - when I have more time I'd like to tie in Serban Ghita's Mobile Detection function as it's more up to date, but this eliminates the miscaching for the time being.