Is the search  box only missing from that one list view  page? If so, the
page has probably been customized (unghosted). Get the Ghost Hunter Web
Part and reghost the page.

If the search box  is missing from everywhere, search this list for how
to troubleshoot search not working.

The search  box is missing from all the pages.

and its also true that in the past, we did used frontpage to
customise the site to great extent.

Any pointers on how to get that search box  back?

After replying your earlier, I started digging more into this problem
and finally managed to find out the solution. Following link which I
found out on this list only, has helped me a lot:
wss.collutions.com/Lists/FAQ/DispForm.aspx?ID=157

You can probably use Ghosthunter & re-ghost the pages. You might
lose some of your customizations,

http://www.bluedoglimited.com/Downloads/pages/Web%20Part%
20Toolkit.aspx