Structurally ordered interfaces between ferromagnetic electrodes and graphene or graphite are of great interest for carbon spintronics, since they allow spin-filtering due to k-vector conservation. By solid phase epitaxy of amorphous/nanocrystalline CoFeB at elevated temperatures, the feasibility of fabricating crystalline interfaces between a 3d ferromagnetic alloy and graphite is demonstrated, without suffering from the unwetting problem that was commonly seen in many previous studies with 3d transition metals. The films fabricated on graphite in this way are found to have a strong body-centered-cubic (110) texture, albeit without a unique, well-defined in-plane epitaxial relationship with the substrate lattice. Using various X-ray spectroscopic techniques, it is shown that boron suppresses the formation of CoFe-O during CoFeB deposition, and then diffuses out of the CoFe lattice. Segregation of B occurred exclusively to the film surface upon in situ annealing, and not to the interface between CoFeB and graphite. This is favorable for obtaining a high spin polarization at the hybrid CoFe/graphite crystalline interface. The Co and Fe spin moments in the crystalline film, determined by X-ray magnetic circular dichroism, are found to be bulk-like, while their orbital moments show an unusual giant enhancement which has yet to be understood.