Yes. You didn't mention what you're doing to reestablish the log chain after you break it by setting the DB to SIMPLE recovery mode. I'm just trying to make sure that you're ok there.

Shifting gears back to the original problem, which edition of SQL Server are you running? If you're running the Enterprise edition, you might be able to avoid rebuilding or even defragging the indexes on certain large parts of the table by using table partitioning. That will give you more time to do the full scans on the parts of the large tables that have actually changed.