We investigate the electronic properties of type-II superconducting Nb(110) in an external magnetic field. Scanning tunneling spectroscopy reveals a complex vortex shape which develops from circular via coffee bean-shaped to elliptical when decreasing the energy from the edge of the superconducting gap to the Fermi level. This anisotropy is traced back to the local density of states of Caroli-de-Gennes-Matricon states which exhibits a direction-dependent splitting. Oxidizing the Nb(110) surface triggers the transition from the clean to the dirty limit, quenches the vortex bound states, and leads to an isotropic appearance of the vortices. Density functional theory shows that the Nb(110) Fermi surface is stadium-shaped near the Gamma point. Calculations within the Bogoliubov-de-Gennes theory using these Fermi contours consistently reproduce the experimental results.