OK, so the only way we were able to get around the issue, was to write an Apex Plug-in

global class flowGetRTId implements Process.Plugin { 

// The main method to be implemented. The Flow calls this at runtime.
global Process.PluginResult invoke(Process.PluginRequest request) { 
        
        String theObject = (String) request.inputParameters.get('Object');
        String theName = (String) request.inputParameters.get('Name');

        // Using the Object and Name provided attempt to find the Record Type
        List<RecordType> theList = [Select Id, DeveloperName, SObjectType from RecordType Where DeveloperName =:theName And SObjectType =:theObject LIMIT 1];
        
        String truncatedId = null;
        if(!theList.isEmpty()){
            truncatedId = String.valueOf(theList[0].Id).left(15);
        }
        // return to Flow
        Map<String,Object> result = new Map<String,Object>(); 
        result.put('RTId',truncatedId);
        return new Process.PluginResult(result); 
    } 

    // Returns the describe information for the interface
    global Process.PluginDescribeResult describe() { 
        Process.PluginDescribeResult result = new Process.PluginDescribeResult(); 
        result.Name = 'flowGetRTId';
        result.inputParameters = new 
           List<Process.PluginDescribeResult.InputParameter>{
               new Process.PluginDescribeResult.InputParameter('Object', Process.PluginDescribeResult.ParameterType.STRING, true),
               new Process.PluginDescribeResult.InputParameter('Name', Process.PluginDescribeResult.ParameterType.STRING, true)   
            };
        result.outputParameters = new 
           List<Process.PluginDescribeResult.OutputParameter>{
               new Process.PluginDescribeResult.OutputParameter('RTId', Process.PluginDescribeResult.ParameterType.STRING)
           }; 
        return result; 
    }

    static testmethod void TestflowGetRTId() {
        flowGetRTId plugin = new flowGetRTId();
        
        // return the Describe results
        Process.PluginDescribeResult thisDescribe = plugin.describe();
        
        // Create default values for each of the expected params
        Map<String,Object> inputParams = new Map<String,Object>();
        
        // As we cannot insert Record Types we must assume that there is a Client Record Type for Accounts
        InputParams.put('Object', 'Account');
        InputParams.put('Name', 'Client');

        Process.PluginRequest request = new Process.PluginRequest(inputParams);  
        
        // Run the plugin
        Process.PluginResult result;
        result = plugin.invoke(request);
        
        // Since we can not insert Record Types testing to verify whether the ID returned is not necessarily repeatable.
        // Therefore we are commenting out the following test
        // System.assertEquals('012700000005bVu',result.outputParameters.get('RTId'));
    } 
    
    static testmethod void testFlowGetRTId_NoResults() {
        flowGetRTId plugin = new flowGetRTId();
        Map<String,Object> inputParams = new Map<String,Object>();
    // Test 1
        // Create params which should not return any Record Types, invalid Object names or missing values
        InputParams.put('Object', 'TestObject1234567890');
        InputParams.put('Name', '');
        
        // Run the plugin
        Process.PluginRequest request = new Process.PluginRequest(inputParams);  
        Process.PluginResult result;
        result = plugin.invoke(request);

        // Verify that NULL is returned
        System.assertEquals(null,result.outputParameters.get('RTId'));
    // Test 2
        // Create params which should not return any Record Types, invalid Object names or missing values
        InputParams.put('Object', 'Account');
        InputParams.put('Name', 'NotARealRecordType');
        
        // Run the plugin
        request = new Process.PluginRequest(inputParams);  
        result = plugin.invoke(request);

        // Verify that NULL is returned
        System.assertEquals(null,result.outputParameters.get('RTId'));
    // Test 3
        // Create params which should not return any Record Types, invalid Object names or missing values
        InputParams.put('Object', 'Account');
        InputParams.put('Name', '');
        
        // Run the plugin
        request = new Process.PluginRequest(inputParams);  
        result = plugin.invoke(request);

        // Verify that NULL is returned
        System.assertEquals(null,result.outputParameters.get('RTId'));
    // Test 4
        // Create params which should not return any Record Types, invalid Object names or missing values
        InputParams.put('Object', '');
        InputParams.put('Name', 'Client');
        
        // Run the plugin
        request = new Process.PluginRequest(inputParams);  
        result = plugin.invoke(request);

        // Verify that NULL is returned
        System.assertEquals(null,result.outputParameters.get('RTId'));