For snobs like the Malfoys, the only thing that would've counted was being part of the Sacred Twenty-Eight. This is a directory of pureblood families, compiled in the early 1930s, by one Cantankerous Nott.
A British real world equivalent would be A Genealogical and Heraldic Dictionary of the Peerage and Baronetage of the British Empire, better known as Burke's Peerage.

Directories such as this exist in several European countries. For instance, The Netherlands have the Nederland's Adelsboek and the Nederland's Patriciaat, Germany has the Genealogisches Handbuch des Adels.
Assuming that pure-blood is modelled at least in part after blue blood, or nobility, Draco wouldn't even need to look up Hermione in any directory. He would've known from growing up in that environment who the pure-blood and 'pure enough'-blood were.
And after all, the wizarding community isn't that big. So anyone not already known to be a witch or a wizard, must be muggle born.
Also, as indicated in this answer, Hermione made no effort to hide it either.