This has always been a problem, since developers have to write an application for many different devices, platforms.
There are many platforms out there and even if you write only for Symbian or J2ME or the newcomer Android you need to take into accounts different screen sizes, different input devices (touch screen? keyboard?), different memories and different accessories (has the device a GPS chip? Bluetooth? Has a fast wireless connection or a slow one?).
[Note: this is also explaining the popularity of the iPhone: same screen, only few devices; But … very small market share].
One way around it was to use a web application, accessible from the native browser, some could be really rich and interactive now. The problem here are the browser (mobile browsers have been historically less advanced than the desktop counterparts) and the fact that the experience still looks not so good as native applications (try it on the iPhone for example).
I am not a huge fan of Flash but I agree that HTML5 will help a lot to improve the experience and hopefully we are really at a turning point.