VLAs were added to C99, but made optional in C11. The reason they were made optional doesn't appear to be in public documents.
The initial proposal to add VLA to C (N637) cited numerical computing as the motivation, and the proposal was based on an existing implementation on Cray platforms. In terms of burden on implementers, a similar feature existed on many platforms via the function
alloca, which is easy to implement on most platforms where the local variables of a function are on a stack that's a contiguous block of memory (which is the case on almost all platforms). Nonetheless, at least one major C implementation cited VLA as a low-priority feature: in Visual C++, they were one of the last missing C99 features and they will not be added.
I think (but I don't have insider information) that the difficulties with VLA aren't in implementations, but for users. VLAs are bug-prone for many reasons. An obvious one is that they can very easily lead to a stack overflow, which often has disastrous consequences (at best a crash, often memory corruption). Another consequence is that innocuous-looking constructs such as
sizeof(...) may now have side effects, and even a simple
sizeof(a) doesn't actually return the size of the array
a if it's a VLA function parameter (that's true if it's a function parameter as well with a static size, but VLAs make it look more like it should work).
Another reason against having VLA in the C standard is that according to John Nagle on comp.std.c,
Prototypes of functions with VLA parameters do not have to exactly match the function definition. This is incompatible with C++ style linkage and C++ function
overloading, preventing the extension of this feature into C++.
C++ is mostly an extension of C; it tweaks some behavior (enough that most idiomatic C programs aren't valid C++) but having a major feature of C that's not in the next edition of C++ is unusual, and is problematic for compilers that handle both languages (which is most C++ compilers).
From personal experience in as a C programmer on embedded platforms, we never use VLAs, even when we're sure that all compilers we care about would support them. They're too bug-prone and they make it impossible to predict your program's stack size (we like to make sure that the deepest nesting of function calls will not overflow the stack — we don't use recursion either). Jens Gustedt on comp.std.c also cites GPUs as a type of platforms where VLAs aren't welcome (I don't know exactly why, but I guess because the memory assigned to each thread's stack tends to be limited).