Q:

Reindexing our store

Our main store has never been indexed and thus we cannot run any reports. 
The stupid contractor that set this thing up was totally incompetent and did things like modify core files and didn't setup the indexing for the site so that reports could be run.
I have a staging site that is setup exactly like it, can I copy my production data to it and then run my reindex on it and then copy the DB to my production site?

A:

First, I'd recommend auditing the codebase and move all the 'hacks' out of core, you'll save yourself headaches when it comes time to upgrade Magento. With that out of the way...
As for the indexing, I'm assuming you're referring to the "Refresh statistics" option under Reports? 
Copying data down and back up can be more chaotic than anticipated with Magento, especially with EAV in the mix.  Your better options would be to make sure the store is running at its best so it can do its job, and execute a full log cleaning and reindexing after off peak times.  Note, If you have 100s of thousands of records (products,sales,customers,etc.) and are having server timeouts, you'll have to fine tune the server or look into more heavy hardware.
A few scripts exist to clean out all the residual data you may have accumulated, however you can find a list of tables most will simply empty or truncate out. 
See: Which database tables can be completely rebuilt via Magento's Reindex All command?
Make sure the cron task has been setup and running properly. Aoe_Scheduler does a good job of this from the an admin point of view. 
Most statistical tables for reports are updated via crontab jobs, so it would be ideal to make sure the cron is running properly.
There is an option to index and clean out the logs via Command Line (CLI), it does a much better job of returning exceptions or errors you may not see when indexing via the admin.
To view status, reindex or list indexes:
php -f shell/indexer.php 
To clean log tables and view table sizes:
php -f shell/logs.php
See the help for each to see what options are available.
You'll also want to review the configuration settings, particularly Advanced > System.

