Como o KPWINC disse, "realmente depende".
Existem vários outros itens que influenciam a resposta à sua pergunta de que uma resposta geral pode não ser apropriada.
O Microsoft MSDN tem entradas para sp_updatestats ( link ) e "UPDATE ESTATÍSTICAS "( link )
Para responder às suas últimas perguntas primeiro:
Você precisa reler a entrada SQLServerPedia. Especificamente:
Your index rebuild will automatically update the statistics for the index (with 100% sample size which is usually better then what you end up with when using sp_updatestats). After the index rebuild is complete you can use sp_updatestats to update the other statistics that require attention (2005+).
Olhando a documentação do UPDATE STATISTICS (2000), diz o seguinte para amostragem:
Note The default behavior is to perform a sample scan on the target table or indexed view. SQL Server automatically computes the required sample size.
Kimberly Tripp reuniu algumas entradas de blog sobre estatísticas, índices e planos de manutenção de banco de dados ( link ). Embora as informações possam ou não ser diretamente utilizáveis por você, a orientação de cada entrada de blog deve ser e os sites referenciados provavelmente serão úteis.