Q:

In which version of WordPress was the new gallery shortcode implemented?

As of WordPress 3.5, as I'm sure you all know, the gallery shortcode generated from the media uploader changed and now includes a list of image IDs.
The gallery shortcode codex page says the following:

"It's important to note that this style of gallery shortcode is not
  new to 3.5, however it is much easier to generate and manage with the
  new Media Workflow introduced in 3.5."

Does anyone know what the minimum WP version is, in which this style of gallery shortcode will still work?

A:

The file /wp-includes/media.php, where the Gallery Shortcode is defined, first appears in WordPress 2.5.
It has the id (singular) attribute to refer to the post_parent:
$attachments = get_children("post_parent=$id ...

The ids (plural) attribute appears in WordPress 3.5, and is used to include attachments:
if ( ! empty( $attr['ids'] ) ) {
    $attr['include'] = $attr['ids'];
}
...
$_attachments = get_posts( array('include' => $include

PS: I've updated the Codex, now it reads (updates in bold):

Since WordPress 2.5 and up until 3.5, the gallery shortcode [...]
  [...]
It's important to note that this style of gallery shortcode is not new to 3.5, previously we could use the include attribute. 

