Ok, I found the problem was with the way I was setting up my IRelationshipClass. I don't remember exactly where I found the example in setting this up, but I was not explicitly stating the Cardinality (for some reason I was using 0, but it did not error, so I believed this was working ok). Anyway this is what you should not do:
pRelationshipClass = pMemoryRelationshipClassFactory.Open("Join", pTable, sTableField, pFeatureLayer.DisplayFeatureClass, sLayerField, "forward", "backward", 0)
You should explicitly state the Cardinality like so:
pRelationshipClass = pMemoryRelationshipClassFactory.Open("Join", pTable, sTableField, pFeatureLayer.DisplayFeatureClass, sLayerField, "forward", "backward", esriRelCardinality.esriRelCardinalityOneToOne)