The most common reasons for a catalog entering the paused state due to space
or memory issues. It will also go in the paused state if you are running it
on a laptop and go to battery power.

Check the gatherer logs to try to find out why.

Recovery normally happens when you reboot or restart MSSearch and MSSearch
mounts the catalogs. There is some restoration here as MSSearch figures out
where it is or was in the indexing process. Normally recovery happens very
quickly. The most common reason I have seen for catalogs remaining in the
recovery state is MSSearch running under a different account than the local
system account.