One question, if I leave the 496 emails on the phone will that stop new ones coming through? Do I have to delete some to get new mail?
As others have said, new ones will always come in.
What's happening is this:-
When you first connected the phone would have downloaded the most recent 500 emails for the account that it hasn't already seen, i.e. the most recent 500 emails.
If you delete any of these from the phone then it wants to download more (older) emails to get you back up to that 500 limit of emails it hasn't shown you before.
So if you delete all of those 500 emails in one go then the phone would download the next oldest 500. Lather rinse repeat until you have eventually downloaded and deleted every email so that the phone has seen them all.
The phone keeps track of the unique identifiers (that the POP3 mail server adds) for each of the emails that it has seen, that way it knows whether to present you with anything new or not.
It's also aware of time though, so even if you've got 500 emails on display (because you told it to show a maximum of 500) then new emails that come in since it last checked will be downloaded to the phone, even if this puts you over the 500 limit.
This is why one of my inboxes (with a 200 email download limit) currently has 1229 new messages indicated on my iPhone. The POP3 Inbox it is connecting to has more than 5000 emails in it (moving this webmail to IMAP and sorting out some basic filtering has been on my TODO list for ages. What I tend to do is download all of the emails using thunderbird [as a backup] and then move all but the last 4 weeks or so into a different folder [on the webmail server]. The biggest blocker is that I've gone from ~5 spams a day to ~200 a day - on an email address I've had for ~20 years - usually the spam calms down after a few weeks but this has been going on for 6 months, so I might need to do something more proactive about it.)
In your situation I'd just mark all of the existing messages as read (rather than deleting them from your phone) and then deal with anything new that comes in as it comes in.
If you want to have no emails in your inbox on your phone for that inbox (i.e. don't want to see anything before now) you're going to have to go through the process of downloading them all and deleting them all, doesn't take too long if you do it in batches of 500 though (and remember to do it over wifi!). That way the phone will have seen every old email and know not to download it again.
Having multiple access points to the same email (mobile, webmail, thunderbird desktop client) via POP3 is manageable when the email volume is low (fewer than 20 a day) but after that it becomes a chore.