We simulate a rotating 2D BEC to study the melting of a vortex lattice in the presence of random impurities. Impurities are introduced either through a protocol in which vortex lattice is produced in an impurity potential or first creating the vortex lattice in the absence of random pinning and then cranking up the (co-rotating) impurity potential. We find that for a fixed strength, pinning of vortices at randomly distributed impurities leads to the new states of the vortex lattice. It is unearthed that the vortex lattice follows a two-step melting via loss of positional and orientational order. Also, the comparisons between the states obtained in two protocols show that the vortex lattice states are metastable states when impurities are introduced after the formation of an ordered vortex lattice. We also show that the existence of metastable states depends on the history of how the vortex lattice is created.