Regardless of which version you're running you can't store 1.2m rows on any given sheet in XL (2003 restricted to 65536 rows, 2007 just over 1m)

Gut instinct... XL is not fit for purpose, certainly not in terms of data storage and yes you should be looking to use a Database.

If you have MS Access then use it if in no other than capacity than as the data warehouse. If needed you can still use XL for analysis using MS Query or ADO to extract data from the db etc... you will with some pretty basic SQL find you can aggregate (ie condense) you data and perhaps circumvent row restrictions ?

You might still want to install XL2007 on your client - though plenty of people would argue that 65536 should be plenty for any XL analysis (ie if you need more you shouldn't be using XL in the first instance)