How large are the databases on which maintenance is being performed? Terabytes??

Are you using Maintenance Plans or custom scripts? In my experience, custom scripts (especially Ola's) are more...

For the tables being queried, when was the last index maintenance performed?

Run a DBCC Showcontig on the tables in question.