Mack32 - You really need to do some fault finding, I would remove EP and reinstall and see if that works, is your product database every big? Check your database for errors, partially delete products, it may be a hosting issue, has it ever worked properly if so what was the last thing you installed and remove that and see if that works!, again has it worked properly before contact your host to see if they have changed/upgraded anything php,mysql etc as this can affect things.
I have had a similar issue when I was with another hosting company since I have moved to Camelot Hosting things are so much better.

dealbyethan.com - I haven't tried this myself but if looks if it is leaving references in the database , I would delete the original record by using '9' in the status column and on the next row insert again the new record in the new category, under the usual status of '1'. Therefore it will completely delete the record and not leave any refs.