So, I'll start by saying I'm not a driver developer, but I have read many comments and docs in this regard.
First of all, we can see how Khronos's own slides on presentation day were mentioning some rather vague "any OpenGL ES 3.1 GPU" (or desktop 4.X). This means something added around that mark would be the secret to it. Compute shaders are definitively [at least one of] the things, being confirmed here, by an Intel developer, and in the spec with no possible unsupported value for MaxComputeWorkGroupSize
and this likely smoking gun:
If an implementation exposes any queue family that supports graphics
operations, at least one queue family of at least one physical device
exposed by the implementation must support both graphics and
compute operations.
In addition to that though, it could also be there are other mandatory capabilities (such as indirect draws or load&store, mentioned in the comments above too). But I have some slight difficulty interpreting the document. With the exception of robustBufferAccess, it seems like just about anything else big you could imagine is optional (from anisotropic filter, to geometry and tessellation shaders, to any special number format other than good old float32)
This being the most hypothetically simple case then, doesn't mean it's all fine and dandy. Not having virtual memory will make your life a hell for example, and lack of other architectural features may basically nullify whatever theoretical advantage in speed the API has.
These links should also answer your wonders about ATi cards. Likely same story for NVidia then (aside of perhaps some microbenchmarks, I'm not sure how much really workable Fermi's 2-years-delayed bare-bones DX12 support eventually is). As for Intel, I don't know what you are talking about, Gen8 is supported since Day1 and in fact even Gen7 shakily works now.
Going even further back, I guess if any the question becomes "what's so special about compute shaders again".
And, well, the thing isn't probably the very specific feature itself (because it's not that you couldn't already do some sort of general purpose calculation even before the unified shader model), but more like the whole general GPU architecture needed to support it. Check this for some backstory.
Before DX11 raised the bar for example, just think that you couldn't even run more than a single "task" on a Tesla GPU, without having to call a context switch (with comparable limitations also likely existing for TeraScale 1 and Gen6). And may God save us from when pixel and vertex units were separated hardware.
fun fact: it turns out that if you are a low-end kind-of-modern mobile gpu (rather than an old desktop card from a time when certain concepts hadn't even been invented yet), engineers can cut you down so much that even if you just sport D3D 9_3 feature level that's still potentially enough to support Vulkan.
EDIT: for such somewhat twisted reasons, it can also happen that while you are just GLES 2.0 compliant (and compute shaders themselves aren't supported atm, even though the architecture would be capable) a restricted version of Vulkan could also be possible. It doesn't give you everything, but it can still lead to benefits over just "old apis".