Ok I've been doing some testing and playing around and I've determined the problem is multi-faceted (pun intended).
Regarding my original post, I've determined the error I was getting was due to user error. For other reasons, in my script I was working with the mesh derived from the topo element via topo.get_Geometry(). The error came when I tried to generate my new boundary point from the midpoint of the edge of the mesh, rather that the actual midpoint between the topo boundary points. Seems if the point was generated from the mesh, it was very very slightly out of tolerance, at least on the large topo I was working on. I couldn't reproduce this with a minimal sample.
But as a result of this, I instead got my new point to add from the midpoint of boundary points themselves, which worked!... sometimes.
First problem: boundary point order
Let's start with a simple topo element created from scratch with 5 points.

Using a script I can label the boundary points (this becomes important later). Apologies for using python, I'm doing my development with pyRevit:
import Autodesk.Revit.DB as DB
uidoc = __revit__.ActiveUIDocument
doc = uidoc.Document
ref = uidoc.Selection.GetElementIds()[0]
topo = doc.GetElement(ref)
points = [pt for pt in topo.GetPoints() if topo.IsBoundaryPoint(pt)]
noteid = DB.FilteredElementCollector(doc).OfClass(DB.TextNoteType).FirstElement().Id
options = DB.TextNoteOptions(noteid)
t = DB.Transaction(doc, 'add point labels')
t.Start()
for i in range(len(points)):
pt = points[i]
DB.TextNote.Create(doc, doc.ActiveView.Id, pt, str(i), options)
t.Commit()

I use this code to add some points to the boundary:
import Autodesk.Revit.DB as DB
uidoc = __revit__.ActiveUIDocument
doc = uidoc.Document
ref = uidoc.Selection.GetElementIds()[0]
topo = doc.GetElement(ref)
points = [pt for pt in topo.GetPoints() if topo.IsBoundaryPoint(pt)]
newpoints = []
for i in range(len(points)-1):
newpoints.append((points[i] + points[i+1])/2)
edit_topo = DB.Architecture.TopographyEditScope(doc, "Edit Topography")
edit_topo.Start(topo.Id)
t = DB.Transaction(doc, "Edit topo points")
t.Start()
topo.AddPoints(newpoints)
t.Commit()
edit_topo.Commit(MyFailureProcessor())
isboundary = 0
isinterior = 0
for p in newpoints:
if topo.IsBoundaryPoint(p):
isboundary += 1
else:
isinterior += 1
print "{} points were created as boundary points".format(isboundary)
print "{} points were created as interior points".format(isinterior)
This is the print result. Everything is as expected.

But when I relabel the points, they are out of order. Adding boundary points messes up the logic for getting the boundary points of a topography surface in order. Maybe there is a better way to go about this?

These out-of-order boundary points are a problem because then when I try to again run the script to add more boundary points, some of the points end up on the interior, as illustrated by the print statement and the view of the points when you 'Edit Surface' of the topo element.


Second Problem: points cannot seem to be added to a topo surface that been split (although I'm not fully confident in this fact because I think I got it to work once somehow)
Here, I've manually split the topo surface and run the script to add boundary points. You can see by the print statement that the added points are all interior points, even though they were added the same way as before and appear to be on the boundary line (as shown in the image)


To conclude, I now have more problems than I started with. I need to be able to add boundary points to a surface that's been split. I also need to be able to do it again, which means I need a more reliable way to get the boundary points in order. I have a workaround to do this with the mesh geometry and some code I wrote, but it means I always have to test the result against the boundary points and regenerate the new point with the boundary points to ensure that it is exactly in the right spot (though this does not matter if the created points won't be boundary points anyway).
EDIT: To clarify, this is in Revit 2020.1. Have not yet tested in newer versions