Is this statement about the challenges of tracking down the Chinese equivalent of a name in Pinyin basically correct?
Yes and no.  The characters associated with context-free random toneless pinyin will sometimes impossible to infer with certainty.  However, the issue is more about identifying characters which match the pinyin, and not really about the possible tone combinations.  Thus, context gives a lot of information as to which characters are appropriate and which are not.
To illustrate, it's unproblematic to understand something like:

Ni jiao shenme mingzi?

despite there being 56 ways of ascribing tones (noting the existence of the neutral tone).  The mental process is basically &quot;think of a common character which has this pinyin and fits the context&quot;, and often there's only one or two such characters.  But for names of people and things its harder to pinpoint.
In the case of Ceres (谷神星), I'd guess a Chinese person who is interested in astronomy will already know the characters (the same way a native English speaker who is interested in astronomy would know &quot;Ceres&quot;, and your average Joe might not know what &quot;Ceres&quot; is).  Someone who had to guess the characters for &quot;Gushenxing&quot; (being aware it's in an astronomical context) would likely get 星 (&quot;heavenly body&quot;) for &quot;xing&quot; correct, and may correctly recognize 谷神 from Chinese mythology.  However, they might also guess 古 (&quot;ancient&quot;) or 姑 (&quot;paternal aunt&quot;) for &quot;gu&quot; and 深 (&quot;deep&quot;) for &quot;shen&quot;.  So it's an overestimate to say there are 43 ways to guess the tones for &quot;Gushenxing&quot; as many of the random tone combinations are not plausible, but the characters are not inferable with certainty.  (And it's possible for Baidu to guess Gushenxing means 谷神星.)
Let's take the surname &quot;Xu&quot; as another example: from CC-CEDICT, there are multiple characters which are used as surnames with the toneless pinyin &quot;Xu&quot;:
徐 徐 [Xu2] /surname Xu/
盱 盱 [Xu1] /surname Xu/
胥 胥 [Xu1] /surname Xu/
藇 藇 [Xu4] /surname Xu/
許 许 [Xu3] /surname Xu/
鄦 鄦 [Xu3] /surname Xu/vassal state during the Zhou Dynasty (1046-221 BC)/

Familiarity with Chinese lets us know it's most likely 徐 or 许, but both of these surnames are common, so it's not possible to be certain how to pronounce a surname written &quot;Xu&quot;.
As an additional point, it's also not uncommon for Chinese people to have rare characters in their names, e.g. I couldn't add three of my co-authors names to my CV because the LaTeX font I used didn't contain these characters (璟 瑀 曌: I replace them with homophones (「景」「雨」「照」)).  So a Chinese person may not even recognize characters used in people's names: sometimes the character itself is not enough.