Keep in mind though that this was in a specific section, and after about 60 hours (yay for turbo mode!) of non-stop random encounters that I fought him. The encounter rate is probably really low.