Some comments...
Detecting the arrival of mail:In principle, the best way to detect the arrival of mail (actually the opening of the mailbox) is to monitor the mailbox door. If it tilts up and down, then a tilt sensor on the door is needed. A nice thing about mounting the tilt sensor inside the door is when the door opens, the sensor is momentarily outside the mailbox with better wireless signaling. If the door swings open horizontally, some type of magnetic switch works better. Tilt sensors typically use a mercury switch allowing a ball of mercury to roll between or away from a pair of contacts. You might also use a load cell under a piece of lightweight material to create a false floor.
Connecting the sensor to Indigo:You have several options all depend on the interface(s) you use to connect Indigo to the outside world. You have discussed Z-Wave and Insteon and you might also consider using an alarm system interface (if you have one) or some custom or home-brew system perhaps using Zigbee or other proprietary wireless systems. Alarm systems work well since they offer a wide range of well powered wireless sensors.
Wired is also possible, and IMHO, preferred. Getting under the sidewalk is really not very difficult. Dig a small hole on each side of the sidewalk and then use a hose and nozzle as a hydraulic drill to connect the two holes. Finally, push a piece of old garden hose trough the hole to act as a conduit.
I'd summarize by saying. choose how you want to sense the arrival of mail first, then worry about the signaling. If you can't get the signaling to work with your first choice sensor, start over, etc. Also, don't forget you will need some means of dealing the signal s from your mailbox. Typically, it is best to have the opening trigger some sort of visible flag (Lamp, keypadlinc button, on screen notice, etc.) which you reset manually after getting your mail.
Good luck and please post back as you progress.