I want to create/edit a desktop icon that must work on Windows, Mac OS X, Linux (KDE/Gnome) and mobile devices. Is there a tool that handles all these different formats?
IcoFX is a free package for creating and editing icons. It works very well in Windows and can also save to 'Macintosh' format; so I'm not sure how well it would work for OS X (I'm not a Mac user). I've been using it with all my Windows stuff for a couple of years now, and have not found it lacking any important features.
EDIT: As pointed out in the comments, IcoFX can't go larger than 256x256, but if you need something larger than that, it's really not an icon anymore. :)
Axialis Software has a top-notch package, Icon Workshop, that can do about anything for any icon. It runs between $30 and $70 US, depending on what you want. I used it for years with great results.
I believe Linux distros use either .png or .svg formats for their icons, so those can be created from most any graphics package.
There is, unfortunately, no such format - both Windows and OS X uses their own propreitary container formats for their desktop icons.
The closest you can get would probably be to use a set of Photoshop plugins such as these to convert your files to the appropriate format and offer both (in addition to PNG for Linux).