So, I mostly agree with the rest of your post, but this point isn't quite as straightforward as you suggest.
The other is that there is no question over the time taken over a deallocation / allocation. It is determined by your code and can be tightly determined - usually a constant very short time.
Malloc/new are not deterministic. The cost of an individual allocation is generally much higher than that of a garbage collector, and it is not a fixed cost. But you do get the (to my mind, dubious) benefit that the performance cost is incurred at the call site (whereas garbage collection incurs a performance cost at an indeterminate later date).
If you actually need deterministic allocation cost, then you have to go with other solutions (probably ahead-of-time allocation: pool allocators, SLAB allocators, etc.)
Ahha .. this may be where the confusion lies.
I didn't want to suggest 'using malloc / free at runtime is better than garbage collectors'. Far from it... they both have related downsides.
In c++, if you override new, you don't need to use OS calls for memory management. You can use whatever system you want for grabbing memory from wherever you want, then you have the opportunity to call the constructor yourself with placement new.
In addition there is a distinction between one off allocation / allocations at startup, and their corresponding deletion at shutdown, and dynamic use (i.e. the kind of things you might use lots of times in a frame). The second case is what we are interested in here. For actually reserving your memory at startup, you could use whatever you want .. an OS heap, garbage collected system. Ultimately your memory has got to come from somewhere.
(There is also the slightly less stringent case of level load / unload, where you *could* if necessary be a bit more lenient / take some shortcuts on some platforms).
What we are after in games, in an ideal world, for dynamic allocation (things that happen a lot rather than just startup and shutdown) is stability (no failed calls) and constant time (and fast) allocation and deallocation.
Sorry I should have been more clear on this. I would on the whole use things like fixed size memory allocators (and potentially other constant time allocators) for things that need to be created / destroyed dynamically (see my first post on page 1). You can use this for constant time incredibly fast allocations / deallocations, suitable for things like nodes in algorithms, even particle type systems.
For things that are truly variable size (levels etc) the tradeoff can be to prereserve space at startup for worst case, and work with that. Alright you lose a bit from the theoretical maximum, but you gain in simplicity and stability. On levels with not much geometry, you can e.g. add more sound, or more textures, and vice versa. For your level file you can prepack into the best format possible, with zero fragmentation, and make use of the whole of your budget in megs. If you need to use more than this, then you need to support streaming of level data on the fly (this is a whole other topic with similar concerns, guess what, you can use fixed size bank slots for this too!).
You can do this for GPU resources too .. reserve e.g. 5000 verts for a character and then stick to that budget or lower for your artwork, and you can guarantee they will always fit in that 'slot'.
You can also pre-designate blank 'slots' for various items in the level data RAM allotment to give more flexibility, if it seems a better idea than deciding ahead of time the maximum number of item 'blah'. If you do this you get the benefit of zero fragmentation, and best use of memory for that level.
In short there are lots of handy 'helper' bits of functionality offered to programmers, like 'general purpose' heaps, variable size strings etc. There are whole languages dedicated to making things 'easier' for the programmer where these things are a given (basic, php etc etc). In most situations this is a real benefit because it makes you much more productive as a programmer - less code, simpler code, less potential for bugs, and the 'costs' are not going to appear to the user.
It's just that in some situations, particularly time critical applications, and those on limited memory devices, it can become worth it to not use some of the helper functionality. An extreme example would be missile control software. You might have limited memory. If your program crashes, people die. If your program takes too long to faff around restructuring the heap, people die. It's only if it works predictably and as per spec that the right people die.
Other examples where you have to be a bit more stringent include things like financial software, medical software, some engineering software.
Would you want the nuke heading towards your neighbours house programmed in java with garbage collection, or c++ with no external allocations? I know know which one I'd rather have heading towards my neighbours. (edit) Some good search terms to google in this area are : 'real time programming', and 'mission critical programming'. (/edit)