The missing tables are created, to quote ArcGIS Help, "in the schema of the connecting user the first time the user makes a selection that exceeds the selection threshold. For ArcGIS for Desktop, this threshold is 100 records."
So why does ArcCatlog try to do a Select when the tables have not been created (or if the user has no schema)?
How would ArcGIS determine if the table had been previously created without executing a SELECT on it? The standard database API doesn't have a "table exists" function, it just returns a NO_SUCH_TABLE on a SELECT. These log messages are not errors, just noise.
One example (there are others) - select exists(Select table_name From information_schema.tables Where Table_Name = 'sde_logfiles' and table_schema = 'test')
Some context - This is a new installation and we are trying to resolve issues that users are experiencing. Distinguishing between noise and valid errors is a step by step process. When you have over 70 connections and each producing this same error, it seems valid to wish for the noise not to be present. We are using the default log settings.