More generally, what early records do we have of his name? Who called him "William the Bastard" (French Guillaume le Bâtard) - was this mostly his Anglo-Saxon enemies?
No one at the time called William ‘the Conqueror’ The earliest recorded use of that nickname occurs in the 1120s, and it didn’t really take off until the 13th century. At the time of his death in 1087, William was called ‘the Great’ by his admirers, and ‘the Bastard’ by his detractors.
To answer the second part of your question: William is indeed called "bastardus" in contemporary sources. However, this refers to the fact that his parents were not married. "Bastard" is not used as a term of abuse until the 19th century.
Bayeux Tapestry which was commissioned by his close associates (either wife or his half-brother, according to various theories) during his life time calls him Willelm, Wilgelm Normanno Duc, Willem Duc, etc., but never the "Conqueror".