The main technical challenges I see are accuracy, survivability, and range. All of these drive cost, since better performance usually requires higher technology, which can get very expensive. On the other hand, as has been mentioned, for tight enough speed requirements, it's not just competitive, it's the only way to succeed.
Accuracy requirements are set by the size of the region you are willing to force the recipient to search. Is within a kilometer good enough, or do you need within 20 meters? If it has to land in the front yard at the correct street address, you have a very costly technology problem; if anywhere in the right city is acceptable, you don't need fancy guidance systems.
By survivability, I mean the thing you are mailing needs to reach the destination intact. The packaging needed to keep paper from being destroyed is quite simple (it's mainly just a box, and some additional paper), but the packaging needed to protect living animals through launch and landing, and possibly re-entry in between, is not. Getting the transported payload safely to the ground might be done best by releasing a package with a parachute, rather than armoring to endure the whole rocket body smashing into the ground at high speed. Parachutes might also help with the accuracy problem, since they provide some additional options unavailable to missiles about to impact, but on the other hand they will slow the process down, and suffer accuracy-degrading environmental effects (such as wind) which are of no consequence to missiles about to impact.
Range is partly a simple expense on its own (you need more fuel to go farther), and partly a difficulty-increasing interaction with the other parameters. For example, if you are using inertial guidance to hit the target, the error induced by bias in an integrating accelerometer grows with time, and thus usually range as well. Similarly, to go farther you may want to go much faster, which would place stricter requirements on surviving launch, re-entry, and landing.
Military surplus is great if you can find it. Some of the most common missile systems around the world are the FROG, with a maximum range of 70 km, and the SCUD, max range 300 km. You can also convert other types of missiles, by changing or even just removing the existing guidance systems -- after all, any surface-to-air missile that misses its target converts itself in flight into a surface-to-surface missile. On the other hand, there really isn't all that much of it: you can probably scrounge a few thousand missiles if you make an all-out effort, but there's no way you're going to be able to gather a million if that's how many you need. At some point, you will have to start manufacturing yourself.
When you do that, you will want to keep 300 km in mind as an important threshold, since the challenge you are about to encounter is diplomacy. In particular, the Missile Technology Control Regime may cause you significant problems in acquiring parts if you cross the line from Category II to Category I, and one of the ways to do that is to exceed 300 km range. There's nothing actually stopping you from making a missile with ranges ten or a hundred times that, but the technology will become much harder to obtain and much more expensive. The other thing to worry about for really long ranges is that once you are launching something with the range of an ICBM, it will probably look a lot like an ICBM while it is being launched and in flight to the destination, which means you have to do something to calm those countries which are monitoring the world for nuclear missile launches (so they can detect and respond to an attack against them), lest you inadvertently start a war.