format() is a nondeterministic built-in string function... right?

The FORMAT documentation has now been updated (in response to your Connect item) to say:

The FORMAT function is nondeterministic.

Likewise, String Functions (Transact-SQL) now includes:

All built-in string functions except FORMAT are deterministic.

A function isn't necessarily deterministic or nondeterministic. There are some functions which can be deterministic depending on how they are used:

The following functions are not always deterministic, but can be used in indexed views or indexes on computed columns when they are specified in a deterministic manner.

CAST and CONVERT are such examples. Based on the testing that you've done so far, I think that it's fair to say that FORMAT is not always deterministic, despite being a string function. If you want to know if it's sometimes deterministic the only technique I can think of is to try enough different ways to call it until you are satisfied. For example, let's consider FORMAT as applied to numbers. There are only ten different numeric input types:

There also appear to be only nine different numeric formats. It's possible to try to create persisted columns for all possible combinations. Some code to do that is below:

DECLARE @FormatValue INT = 76767; -- change this if you want
DECLARE @FormatCulture VARCHAR(10) = 'en-US'; -- change this if you want
DECLARE @Format VARCHAR(1);
DECLARE @FormatType VARCHAR(10);
DECLARE @SQLForColumn VARCHAR(200);
DECLARE @TestNumber INT = 0;

BEGIN

    DROP TABLE IF EXISTS dbo.TargetTable;
    CREATE TABLE dbo.TargetTable (ID INT);

    DROP TABLE IF EXISTS #ColumnAddResults;
    CREATE TABLE #ColumnAddResults (
    FormatType VARCHAR(10),
    [Format] VARCHAR(1), 
    Succeeded VARCHAR(1), 
    ErrorMessage VARCHAR(1000)
    );

    drop table if exists #Types;
    create table #Types (FormatType VARCHAR(10));

    INSERT INTO #Types VALUES
    ('bigint'), ('int'), ('smallint'), ('tinyint'), ('decimal')
    , ('numeric'), ('float'), ('real'), ('smallmoney'), ('money');

    drop table if exists #Formats;
    create table #Formats ([Format] VARCHAR(1));

    INSERT INTO #Formats VALUES 
    ('C'), ('D'), ('E'), ('F'), ('G'), ('N'), ('P'), ('R'), ('X');

    DECLARE format_statements CURSOR LOCAL FAST_FORWARD FOR 
    SELECT #Types.FormatType, #Formats.[Format]
    FROM #Formats
    CROSS JOIN #Types;

    OPEN format_statements;

    FETCH NEXT FROM format_statements   
    INTO @FormatType, @Format;  

    WHILE @@FETCH_STATUS = 0  
    BEGIN
        SET @TestNumber = @TestNumber + 1;
        SET @SQLForColumn = 'alter table dbo.TargetTable add NewColumn' + CAST(@TestNumber AS VARCHAR(10))
        + ' as FORMAT(CAST(' +  CAST(@FormatValue AS VARCHAR(10)) + ' AS ' + @FormatType + '), '
        + '''' + @Format + ''', ''' + @FormatCulture + ''') persisted';

        BEGIN TRY
            EXEC (@SQLForColumn);
            INSERT INTO #ColumnAddResults VALUES (@FormatType, @Format, 'Y', NULL);
        END TRY
        BEGIN CATCH
            INSERT INTO #ColumnAddResults VALUES (@FormatType, @Format, 'N', ERROR_MESSAGE());
        END CATCH;

        PRINT @SQLForColumn;

        FETCH NEXT FROM format_statements   
        INTO @FormatType, @Format;  
    END;

    CLOSE format_statements;  
    DEALLOCATE format_statements;  

    SELECT * FROM dbo.TargetTable;
    SELECT * FROM #ColumnAddResults;
    DROP TABLE #ColumnAddResults;

END;

Here's a sample of the output:

I wasn't able to get any of the columns to be added to the table for a few input values and cultures. I did not exhaustively try all possible cultures because I can't find a list of them within SQL Server.

At minimum it seems safe to conclude that the documentation regarding the determinism of FORMAT is incorrect, so I would recommend submitting a connect item for it.