In this work, we propose two search-based approaches based on the tabu search to explore the solution space for low leakage power data-paths. The first approach explores different schedules. The second approach simultaneously searches for schedules and mappings that dissipate low leakage power. Our approaches identify data-paths which dissipate upto 40% lesser leakage power than those synthesized using traditional heuristics. Tabu search finds significantly better solutions at the cost of a moderate increase in computation time.