Well technically pure-bloods are just people with no known muggle relatives.It doesn't mean there wasn't a muggle in there somewhere.So if a half-blood were to marry a pure-blood the child would be half-blood since there are known muggle relatives.
My best guess is that a wizard or a witch or a squib married someone generations back. They inhereit it from an ancestor.And since the magical gene is much stronger then the human gene, it is passed on and on and on.....until one day, a Muggleborn is born. The rule applies to everyone in the magical world. Pure-bloods think there are no muggles in their family trees when there are,so whose to say there are no wizards,witches or squibs in muggle family trees?Just because you can't find it doesn't mean it's not there.