For anyone having this issue in the future, the problem seems to have been that I had two folders, "Sent" and "Sent Messages."
On iOS the local "Sent" folder was associated with the online "Sent" folder, whereas webmail and my desktop client were using "Sent Messages."
Not sure how this happened in first place, but I've moved all the messages from the "Sent Messages" folder to "Sent" and relinked which folder the email client should look for.
Changing the folder on iOS was going to be more of a pain, so sorting the desktop client was simpler.