Mutations have to happen sometime, and when they do, brothers will be different. Very occasionally, brothers will even differ on more than one marker.
The best way to validate the relationship is with an autosomal test. Half-brothers share about 25% of their DNA on the average. 23andMe would be a good choice for this test, since you can see exactly where the brothers match.