Right, so I think I've roughly worked out the process, please feel free to comment, or correct if you find this is inaccurate:
It appears that deleting from google photos (at least on my Galaxy S5, and Tab 3) does not delete the original. My photos are held on the external SD card on both devices. Not sure whether this matters. Having deleted the photos on the web, I can still see the originals in my camera folder. I'd be extremely cautious attempting this test on a stock Android phone as it may be different.
What deleting does do, is it seems to retain the record of the file on their server. So even when I cleared app data after deleting the photos, and backing up again, the photos did not back up.
Now what I have found useful, is that despite this shortcoming on Android (may be a workaround somehow, perhaps going a step further and deleting the app?), I can import the previously deleted photos onto a computer, and upload via the Photo Backup service, or manually via the web app.
I think it's theoretically plausible that I could delete all my smaller photos uploaded previously and re-upload without issue, but I think I'm going to do them slowly and carefully.
I wish Google would provide a bit more insight into how Photos checks that a photo has been previously uploaded (and perhaps deleted) but I hope this is helpful.