A short, mathematical answer to the question is found in the properties of Fourier transforms. The temporal response of the environment to a perturbation is given by the Fourier transform of its frequency response to the same perturbation. Therefore, if a broad range of frequencies in the bath are perturbed, the response occurs over a narrow range of times. Let me try to briefly explain how this mathematical structure arises from the physics.
Spontaneous emission can be understood from the following hand-wavy arguments. The electron in an excited state produces an electric field. This field fluctuates over time; these fluctuations drive the transitions in the electronic state. The spontaneous emission therefore arises from the effect of the electron on its environment, which in turn produces a back-action that affects the electron.
The response of the electromagnetic field to a perturbation $\mathbf{E} = E\hat{\mathbf{z}}$ (I have arbitrarily chosen polarisation in the $z$ direction) is captured by the response function:
$\Gamma(t) = \langle E(t) E(0)\rangle,$ where $E(t)$ denotes the Heisenberg-picture operator. This function is central to the theory of linear response to a small perturbation. For example, if one introduces a classical electric dipole that oscillates with a time-dependent dipole moment $d(t)$, the resulting electric field at that point is given by the convolution
$$ \delta\langle E(t) \rangle \approx -i\int_0^t\mathrm{d}s\; d(t-s) \Gamma(s).$$
The previous paragraphs serve merely to motivate the appearance of the response function $\Gamma(t)$. In a physically realistic case where we have a quantum dipole (e.g. an atom) with two states separated by a frequency $\epsilon$, the response function determines the rate of spontaneous emission, which is proportional to the quantity:
$$ \gamma(t) \sim \int_0^t\mathrm{d}s\; e^{i\epsilon s} \Gamma(s). $$
Assuming that $\Gamma(s)$ decays much more rapidly than $1/\epsilon$, for times $t\gg 1/\epsilon$ we can make the Markov approximation
$$ \gamma(t) \to \gamma = \int_0^{\infty}\mathrm{d}s\; e^{i\epsilon s} \Gamma(s), $$
so that we effectively have a constant spontaneous emission rate over time, leading to pure exponential decay.
When does $\Gamma(s)$ decay rapidly enough so that we can make the Markov approximation? The electric field $E(t)$ contains many components (normal modes) which oscillate at different frequencies. If we make this decomposition we get a Fourier representation like
$$\Gamma(t) = \int_0^\infty\mathrm{d}\omega\; e^{-i\omega t} J(\omega),$$
where the spectral density $J(\omega)$ quantifies the degree to which the field at frequency $\omega$ is perturbed by a dipole. For an atom interacting with the electromagnetic field in free space, you will normally get something like
$$J(\omega) \sim \lambda \frac{\omega^3}{\omega_c^2}e^{-\omega/\omega_c}.$$
Here $\lambda$ is a small dimensionless coupling parameter, and $\omega_c$ is a large frequency cutoff on the order of $c/a_0$, where $a_0$ is the Bohr radius. From purely dimensional arguments you can see that
$$ \Gamma(t) \sim \frac{\lambda \omega_c^2}{(\omega_c t)^4}. $$
This tells you that $\Gamma(t)$ vanishes after times much bigger than $\tau = 1/\omega_c$. This time $\tau$ is called the memory time. Since here $\omega_c \approx 10^{18} \text{Hz}$, while the typical optical frequencies are $\epsilon \approx 10^{14} \text{Hz}$, the Markov approximation is well justified.
The extreme example of Markovian noise (white noise) corresponds to $J(\omega) = \text{const.}$, in which case $\Gamma(t) = \delta(t)$, i.e. the bath memory time is infinitesimally small. The opposite extreme is something like a photonic crystal, where the environment has a sharp band edge at frequency $\Omega$ where $J(\omega)$ goes to zero. In that case the response function ends up something like
$$ \Gamma(t) = \int_0^\Omega e^{-i\omega t} J(\omega) \sim f(t) e^{-i\Omega t}$$
where $f(t)$ is some function of time. Now if $\Omega$ is comparable to $\epsilon$, you can imagine that there will be resonance effects, and there will be no smooth irreversible transfer of energy into the environment. Rather $\gamma(t)$ becomes a complicated function of time and you will see non-Markovian dynamics. If the frequency $\epsilon$ lies deep within the band-gap then there is no spontaneous emission at all, since there are simply no electromagnetic field modes to couple to, i.e. effectively $J(\omega) = 0$ in the relevant frequency range.
Hopefully these examples should convince you that the frequency scale which sets the bandwidth of perturbed modes in the environment ($\omega_c$, $\Omega$) is on the order of the inverse memory time. Thus, large bandwidths correspond to shorter memory times, i.e. more Markovian environments.
DISCLAIMER: All equations given here are based purely on memory and minimal back-of-the-envelope consistency checks. The proportionality factors and various terms which I arbitrarily deemed irrelevant are almost certainly missing.
