One of the problem with the mobile fragmentation is that the icon size used is different. There is no minimum size specified, and it is up to the platform to resize the icon. As such, if you want a perfect looking icon for a MIDlet, the only way to do it is to know the size that the phone support.
A good reference is from j2me wiki.
Here is an extracted (from mobilepit) icon size guideline for different devices
Nokia
- Series 40 - 128x160=24x24, 208x208=46x46, 240x320=46x48
- S60 1st and 2nd - 176x208=42x29, 352x416=76x76
- S60 3rd - 176x208=31x31, 208x176=37x37, 352x416=76x76, 240x320=53x53/55x55, 320x240=52x52/54x54, 208x208=37x37
- N90/N95 : 84x58
Samsung & Sony Ericsson
Most Samsung phone accept 16x16, 32x32 icon size
Motorola
15x15, 16x16, 32x32