We determine magnetoresistance effects in stable and clean Permalloy nanocontacts of variable cross section, fabricated by UHV deposition and in situ electromigration. To ascertain the magnetoresistance (MR) effects originating from a magnetic domain wall, we measure the resistance values with and without such a wall at zero applied field. In the ballistic transport regime, the MR ratio reaches up to 50% and exhibits a previously unobserved sign change. Our results can be reproduced by recent atomistic calculations for different atomic configurations of the nanocontact, highlighting the importance of the detailed atomic arrangement for the MR effect.