The search bit would be free, so i was hoping that sellers would share their both their successful and unsuccessful transactions. To prevent spurious data the seller would have to provide postal tracking numbers.

Buyers would be given the chance to claim their address and associated 'delivery' reputation. This lets them take their reputation with them when they move. Periodically the buyers would receive a letter from the service just to confirm they are still at the said address - proof required also.

I guess these are some of the problems that need resolving if this service was to fly. There's definitely a large problem here but maybe this approach isnt the silver bullet.