This page generates web site icons with a test pattern designed to show how icons are scaled on iPhone/iPod and thus detect the native size of the icons.
To test icon rendering on your iPhone/iPod, click the links until you get to the size you want, then touch "add bookmark", then "add to home screen", at which point you will see a preview of the icon. You don't actually need to save it, just click cancel to go back.
The grid pattern will make any scaling very obvious. At the native size, you should see a clear grid, all lines and cells visible with even spacing across the image in both directions, no unevenness or moiré patterns (try 55x57 for an example). The diagonal line may be drawn with gaps in - that seems to be a bug in PHP's GD library.
As far as I can tell, there isn't a native integer image size. It looks like it's between 59 and 60 pixels, and may not be square. 60x60 gives a fairly clean result with single vertical discontinuity, 59x59 has a slightly worse looking horizontal discontinuity. At larger sizes, the artefacts pretty much disappear into the scaling fuzz, so while larger images will give smoother results, they won't be as sharp as an exact match to a native size.