I personally feel this is a real pain point. Forget about US/AUS/UK - but there is really need in domestic too. Think about more frequent routes like BLR-HYD, BLR-DEL, DEL-MUM, DEL-KOL & others. And you do not need to be limited to air travel. Of course, the International problem is much larger than this.
As people rightly questioned and expressed the concern of "trust", which is the most important and toughest to solve. To get started, how about a platform for senders to post their requirements and takers can pick them up based on the price quoted (or maybe reverse).
To build the first level of trust:
- limit the products (ex: only laptops/food/clothes)
- leverage social profiles like FB, Twitter, LinkedIn along with common friends/school.
- provide a rating system for both the users (just like Uber)
- collect ID proof, address proof and verify phone number on signup.
- sender should upload photos of the item (open box, closed box just like in OLX) along with item description, weight, dimensions etc so that the taker can decide to pick it up or not.
- create a trust score (something like badges/levels)
- ask the sender to upload information about the receiver(s) - a simple FB tagging should do and you get to know more information about the receiver too, which needs to be shared with taker later.
Now, that there is so much information exchange between the two parties, you can mask the names and exchange only after an advance payment is done and later release the amount once the sender marks it as completed. You can take a small cut in the transaction.
Once you reach critical mass, you can get a bit deeper. To solve the problem of delays on both sides (can be a premium service), you can setup a small stall where the products will be dropped (ex: at major airports/bus stops) and give to the receiver/taker based on verification.