Just to be sure for anyone who reads this thread in the future:

bitcoind listtransactions "*" COUNT FROM will return an array of transactions which is a subset starting at the FROMth transaction (starting from the most recent transaction) and will fetch COUNT entries which are older than that one.

I had mistakenly thought that it fetched entries which are more recent than the FROM point and that the FROM point was measured from the oldest transaction.

The correct solution to my problem is

bitcoind listtransactions "*" 1 X
for x starting at 0 and increasing by 1 until the result matches a transaction I've already encountered before

This will fetch one entry at a time from the newest to the oldest. Therefore it is sensible to stop at some point.

Just wanted to make sure I wasn't passing on my misinterpretation of how listtransactions works