The MaxSumSum (maximum diversity) problem consists of the selection of p facilities among n candidate locations in a way that the total sum of the distances between each pair of the located facilities is maximized. The Basic Variable Neighborhood Search heuristic (BVSN) has already been applied to solve this problem with success. In this work we have developed a Greedy Variable Neighborhood Search heuristic which adds a new type of plateau search mechanism to its general framework. This newly incorporated local search technique helps the exploration of the solution space and facilitates finding higher quality solutions. The proposed solution procedure further improves the already high performance of the BVNS and finds new improved solutions for several of the largest benchmark datasets in the literature.