In Indonesia, the tenure arrangement and utilization of the coastal areas are influenced by different regimes. Land regime, coastal and small islands regime, maritime regime - and sometimes by forest-land regime, take place simultaneously although on different scales of influence. This is where the complexity arises which, if directed to a sustainable living space arrangement through the framework of coastal agrarian reform, will encourage the need for more detailed thinking in terms of mechanisms for strengthening property rights through the function of land administration. Moreover, so far it is known that our land administration policy is too focused and gravitated on land-area parcels and neglects land parcels on the coast, or commonly known as aquatic land parcels. This paper will discuss our study carried out in regulatory and technical aspects in finding the most flexible form of tenure in strengthening tenure security for coastal communities. The study therefore brings and explores trade-offs between community perceptions, land tenure regulations and spatial planning regulations, within the study area on the coast of Tanjungpinang, Riau Islands.