Le temps machine requis pour une analyse en maximum de parcimonie (comme pour les autres méthodes) est proportionnel au nombre de taxa et de caractères inclus dans l'analyse. Ainsi, puisque plus de taxa requièrent plus de branchements et de topologies à estimer, une plus grande incertitude doit être attendue dans les analyses de grande ampleur. L'échantillonnage des taxa (et leur séquençage a fortiori) est coûteux en temps et en argent, la plupart des analyses phylogénétiques n'incluent qu'une fraction des taxa qui auraient pu être échantillonnés.
Des études empiriques, théoriques et des simulations ont conduit à démontrer l'importance capitale d'un échantillonnage rigoureux et adéquat. Ceci peut être résumé dans l'énoncé suivant : une matrice phylogénétique a pour dimension nombre de taxa x nombre de caractères. Doubler le nombre de taxa, double la quantité d'informations présentes dans la matrice, comme en doublant le nombre de caractères. Chaque taxon représente un nouvel échantillon pour chacun des caractères, mais, plus important, il représente une nouvelle combinaison des états de caractères. Ces caractères peuvent ne pas déterminer uniquement où se branche sur l'arbre phylogénétique le nouvel échantillon, mais peut influer sur l'analyse dans son intégralité, causant potentiellement des remaniements dans les relations évolutives précédemment obtenues sur les autres taxa, par exemple en changeant les patrons d'estimation des changements de caractères.
La plus évidente faiblesse des analyses en Maximum de Parcimonie est celle de l'attraction des longues branches (voir plus bas), particulièrement forte dans le cas d'un échantillonnage peu robuste (le cas extrême étant le cas d'un jeu de données de 4 taxa, minimum pour obtenir un arbre non raciné qui fasse sens). Cette attraction des longues branches représente le cas classique où l'ajout de caractères additionnels n'améliore pas la qualité de l'estimation. Quand l'on rajoute des taxa, les longues branches sont « rompues », en améliorant l'estimation des changements d'états de caractères, le long de ces branches phylogénétiques. En d'autres termes, il est possible dans certains cas d'obtenir une inférence phylogénétique satisfaisante, avec des centaines de taxa, en n'utilisant que quelques centaines de caractères.
Bien qu'un large nombre d'études aient été réalisées à ce sujet, il reste des progrès conséquents à réaliser en matière de stratégie d'échantillonnage. Avec l'augmentation des capacités de calcul informatiques et la décroissance des coûts (en temps et argent, grâce à l'automatisation des processus de séquençage) de l'obtention et du traitement d'un jeu de données conséquent, les études traitant de centaines de taxa et de plusieurs milliers de paires de bases (kB) deviennent courantes. Les observations empiriques doublent les progrès réalisées en modélisation/simulation et les stratégies d'échantillonnage et d'analyse s'affinent d'année en année (pas uniquement pour le Maximum de Parcimonie).
Il est également possible en Maximum de Parcimonie d'appliquer des pondérations différentes à des caractères individuels. Traditionnellement on applique ces pondérations relativement à un « coût évolutif » unitaire. Certains caractères seront donc considérés comme un meilleur reflet des « vraies » relations évolutives entre taxa, et seront donc pondérés par 2 ou plus. Les changements de ces caractères seront comptabilisés comme 2 plutôt qu'un seul, dans le calcul du score (voir plus haut). La pondération des caractères a été source d'un large débat. Le cas le plus souvent observé est une pondération égale pour tous les caractères, bien que les exceptions soient courantes. Par exemple, la troisième position d'un codon est connue pour être particulièrement labile (à cause de la synonymie importante du code génétique, concernant cette position) et peut être sous pondéré à cause de cette considération (en raison de la forte homoplasie potentielle de ces 3èmes positions). Dans certains cas, bien que l'on puisse y voir un raisonnement circulaire, des analyses peuvent être conduites en repondérant les caractères suivant les degrés d'homoplasie que l'on trouve dans une première analyse.
Les changements de caractères peuvent être également pondérés individuellement. C'est souvent le cas pour les données de séquences nucléotidiques. Empiriquement, il a été montré que certaines occurrences de changements de bases étaient plus fréquentes que d'autres. Cette réalité trouve ses soubassements dans les natures biochimiques des bases et leurs réactions aux agents mutagènes, qu'ils soient transcriptionnels, physiques ou chimiques. On sait par exemple que des transitions entre purine et pyrimidine sont plus fréquentes que les transvertions, c'est-à-dire un changement de bases accompagné d'un changement de famille chimique.