Does the recipient of my email have to use Polymail for Tracking to work?

Not at all! The email tracking will work regardless of how your recipient checks his/her email. We're also constantly improving tracking, developing its capabilities on other email clients.