We consider the problem of preprocessing an edge-weighted tree T in order to quickly answer queries of the following type: does a given edge e belong in the minimum spanning tree of T \cup \{ e\}? Whereas the offline minimum spanning tree verification problem admits a lovely linear time solution, we demonstrate an inherent inverse-Ackermann type tradeoff in the online MST verification problem. In particular, any scheme that answers queries in t comparisons must invest \Omega (n\log \lambda _t (n)) time preprocessing the tree, where \lambda _t is the inverse of the t^th row of Ackermann?s function. This implies a query lower bound of \Omega (\alpha (n)) for the case of linear preprocessing time. We also show that our lower bound is tight to within a factor of 2 in the t parameter.