diff --git a/compiler/mark_tail_calls.m b/compiler/mark_tail_calls.m
index 7f67e6b00..686eae9a7 100644
--- a/compiler/mark_tail_calls.m
+++ b/compiler/mark_tail_calls.m
@@ -218,7 +218,6 @@
 :- import_module hlds.code_model.
 :- import_module hlds.hlds_error_util.
 :- import_module hlds.hlds_goal.
-:- import_module hlds.hlds_proc_util.
 :- import_module hlds.mode_top_functor.
 :- import_module hlds.proc_info_types.
 :- import_module hlds.type_util.
@@ -487,19 +486,20 @@ get_params_for_llds_code_gen(Globals, Params) :-
 
 do_mark_tail_rec_calls_in_proc(Params, ModuleInfo, SCC, PredId, ProcId,
         PredInfo, !ProcInfo, WasProcChanged, !Specs) :-
-    proc_info_interface_determinism(!.ProcInfo, Detism),
-    determinism_components(Detism, _CanFail, SolnCount),
-    (
-        % For at_most_zero procedures, there is no point in handling tail calls
-        % specially.
-        SolnCount = at_most_zero,
-        WasProcChanged = proc_was_not_changed
-    ;
-        ( SolnCount = at_most_one
-        ; SolnCount = at_most_many
-        ; SolnCount = at_most_many_cc
-        ),
-
+    % For a long time, we simply returned proc_was_not_changed for
+    % SolnCount = at_most_zero procedures, on the grounds that
+    %
+    % - such procedures should be executed very rarely,
+    % - their codes should not be recursive, and even if they are,
+    %   they should not be *deeply* recursive,
+    % - meaning that their main cost was their code size, and
+    %   not their execution time, and
+    % - in the MLDS backend, the main user of this module, tail recursion
+    %   optimization requires extra wrapper code around procedure bodies.
+    %
+    % We stopped doing that due to a report on m-users on 2026 sep 14
+    % of a recursive procedure with determinism "erroneous". The extra cost
+    % in memory is negligible.
     Params = tail_rec_params(MaybeSelfFeature, MaybeMutualFeature,
         MaybeRecordTailCalls, WarnNonTailRecParams),
     ( if
@@ -545,7 +545,6 @@ do_mark_tail_rec_calls_in_proc(Params, ModuleInfo, SCC, PredId, ProcId,
         ),
         !:Specs = GoalSpecs ++ !.Specs,
         WasProcChanged = proc_may_have_been_changed
-        )
     ).
 
 :- pred find_output_args(module_info::in,
@@ -936,7 +935,7 @@ mark_tail_rec_calls_in_plain_call(GoalExpr0, GoalInfo0, Goal,
             false
         )
     then
-        !Info ^ mtc_any_rec_calls := found_any_rec_calls,
+        !Info ^ mtc_any_rec_calls := found_some_rec_calls,
         AtTail0 = at_tail_info(Laters0, OutputVars),
         ( if
             set_tree234.is_empty(Laters0),
@@ -1410,7 +1409,7 @@ warning_pieces_about_later_op(Later, Pieces) :-
     %
 :- type found_any_rec_calls
     --->    not_found_any_rec_calls
-    ;       found_any_rec_calls.
+    ;       found_some_rec_calls.
 
     % maybe_report_no_tail_or_nontail_recursive_calls(PredInfo, ProcInfo,
     %   FoundAnyRecCalls, Context, !Specs):
@@ -1428,7 +1427,7 @@ warning_pieces_about_later_op(Later, Pieces) :-
 maybe_report_no_tail_or_nontail_recursive_calls(PredInfo, ProcInfo,
         FoundAnyRecCalls, !Specs) :-
     (
-        FoundAnyRecCalls = found_any_rec_calls
+        FoundAnyRecCalls = found_some_rec_calls
     ;
         FoundAnyRecCalls = not_found_any_rec_calls,
         proc_info_get_maybe_require_tailrec_info(ProcInfo,