Reply To: Emails being sent to spam

That could be the reason, but in that case this problem would be far more spread and not being reported first after years. You can change it in /lib/classes/reservation.class.php.
Change

Select Code
1
$headers = "From: \"".$this->name."\" email.">\n";

to

Select Code
1
$headers .= "Reply-To:  ".$this->email."\n";

And please tell me if it fixes it. If not try to use the smtp plugin to force them get send over the right server.
Regards