Thanks for your ideas and comments on this one.
Basically, there is no such thing as a social security number in PNG. The government is currently trying to introduce a national ID card but is still some years away. Furthermore, peoples names can change from visit to visit (the concept of a fixed name is a very alien concept to many tribal folks around the world - not only PNG). The concept of uniquely ID'ing a patient easily is therefore a pre-req for any HIS in this part of the world.
If anyone on this forum has been faced with the same challenge we are open to ideas.