I don't have too much to add... but AFAIK the ipod uses the HFS+ filesystem which I beleive that OSX uses. If you can find some data recovery utilities that will work on mac and have access to a mac running OSX, then maybe you can mount it and recover it?

This is possibly why the recovery is so expensive?

There are drivers for linux to mount the ipod filesystem... as I'm sure there are with windows too. I just don't know if the recovery utilities that work on *nix or m$ will be able to search and recover from the HFS+ filesystem. I just didn't do enough research...