I searched all over for a solution to avoid hardcoding internalId's. Even NetSuite support failed to give me a solution. Finally I stumbled upon a solution in NetSuite's knowledgebase, getCustomizationId.
This returns the internalId, scriptId and name for all customRecord's (or customRecordType's in NetSuite terms! Which is what made it hard to find.)
public string GetCustomizationId(string scriptId)
{
// Perform getCustomizationId on custom record type
CustomizationType ct = new CustomizationType();
ct.getCustomizationTypeSpecified = true;
ct.getCustomizationType = GetCustomizationType.customRecordType;
// Retrieve active custom record type IDs. The includeInactives param is set to false.
GetCustomizationIdResult getCustIdResult = _service.getCustomizationId(ct, false);
foreach (var customizationRef in getCustIdResult.customizationRefList)
{
if (customizationRef.scriptId == scriptId) return customizationRef.internalId;
}
return null;
}