I'm especially interested how long it would take to restart a turbofan engine after a hypothetically erroneous shutdown of an engine immediately after takeoff i.e., at an altitude at which the air is reasonably dense. Is windmilling enough or would you need crossbleed and starters again?
It can take from a few seconds to eternity. If the core cools down, the engine might lock up.
Windmilling starts are only possible if the aircraft is flying fast and low enough. It will assist the startup process, but needs additional help from the starter or bleed air, typically below 300 knots and above 20,000 ft. Details vary from type to type. If everything works as designed, a windmilling assisted restart is faster than a regular engine start.
The ability to restart in flight must be proven as part of the certification process. However, right after takeoff the speed is too low for a pure windmilling start, and an additional energy source is needed.
Right after takeoff bleed air would be necessary to restart, preferably from the APU if thrust reduction on the operating engine is unacceptable in the current phase of flight.
I only have data for the Rolls Royce Allison AE3007 A series engines and the windmilling envelope at all altitudes is between 260 KIAS and Vmo/Mmo with the additional limitation that N2 must be above 10%. An aircraft that has just taken off will not be going this fast so an assisted (bleed air) start is the only viable option.
How long the start will take depends on the particular engine, but all turbines (that I'm aware of) have a maximum start time limitation. The engine discussed above on the EMB-145 has a 60 second limitation on starting. Based upon my experience starting the engines with a stiff headwind, I'd assume that an APU start at flying speeds would probably take around 35-40 seconds in the EMB-145. By the book the engine needs another minute before significant thrust is applied.
All of the above information is specific to one airframe/engine combination and will vary for other aircraft and engines.