Sam at Javablog certainly has a very valid point.
Versign certificates for MIDP are not available in all phones.
When they are available, they usually make your MIDlet belong to a "trusted third-party" security domain.
These days, there are typically 2 security domains with better access to permissions: "operator" and "manufacturer".
Getting your application signed by a mobile network operator is obviously only useful when you want to deploy it on a phone subsidised by that operator.
To be fair, operators will sometimes sign MIDlets with certificates that will work on phones sold in several countries.
I don't think operators got so powerful that handset manufacturer certificates were ever not included in actual phones sold to the public.
If you plan on wide deployment of your MIDlet, clearly, getting it signed by only one device manufacturer is not that great a strategy.
Signing stategies usually go hand in hand with choosing which market to target.
For a small controlled deployment, verisign signing may be enough, especially if your application isn't doing anything too sensitive.
To address the entire worldwide market, you will need to deploy many different versions of your application, each signed according to the target handset. In that case, you will at least need relationships with several MNOs and relationships with manufacturers won't hurt either.
The signing issue is only one of the fragmentation hurdles of large-scale MIDP development but it's the one that can't be addressed with just technical solutions.