kubernetes: Deployment with recreate strategy does not remove old replica set

I want to replace an application by running a new deployment. The image tag however does not change, although the image itself might have (that’s the reason for the image pull policy always). For that reason I’ve added an extra label that changes on every deployment.

---
apiVersion: extensions/v1beta1
kind: Deployment
metadata:
  name: gocd-agent-${AGENT_NAME}
spec:
  replicas: ${AGENT_REPLICAS}
  strategy:
    type: Recreate
  revisionHistoryLimit: 25
  selector:
    matchLabels:
      app: gocd-agent-${AGENT_NAME}
      release: v${VERSION}
  template:
    metadata:
      labels:
        app: gocd-agent-${AGENT_NAME}
        release: v${VERSION}
    spec:
      containers:
      - name: gocd-agent
        image: ${AGENT_IMAGE}
        imagePullPolicy: Always
        volumeMounts:
        - name: ssh-keys
          mountPath: /var/go/.ssh
        - name: gcloud-keys
          mountPath: /var/go/.gcloud
        - name: docker-sock
          mountPath: /var/run/docker.sock
        - name: docker-bin
          mountPath: /usr/bin/docker
        env:
        - name: "GO_SERVER"
          value: "gocd-server"
        - name: "AGENT_KEY"
          value: "something"
        - name: "AGENT_RESOURCES"
          value: "${AGENT_RESOURCES}"
        - name: "DOCKER_GID_ON_HOST"
          value: "107"
        resources:
          limits:
            cpu: 1000m
            memory: 1024Mi
          requests:
            cpu: 10m
            memory: 512Mi
      volumes:
      - name: ssh-keys
        secret:
          secretName: ssh-keys
      - name: gcloud-keys
        secret:
          secretName: gcloud-keys
      - name: docker-sock
        hostPath:
          path: /var/run/docker.sock
      - name: docker-bin
        hostPath:
          path: /usr/bin/docker

When applying this the deployment is accepted and a new replica set is created. However the old replica set stays alive as well.

I apply it with the following command in order to replace the variables. Take note of how the version is set to the current date and time.

AGENT_NAME=$AGENT_NAME AGENT_REPLICAS=$AGENT_REPLICAS AGENT_IMAGE=$AGENT_IMAGE AGENT_RESOURCES=$AGENT_RESOURCES VERSION=$(date +"%Y%m%d%H%M") sed -r 's/^(.*)(\$\{[A-Z_]+\})/echo "\1\2"/e' ./manifests/gocd-agent-deployment.yaml | kubectl apply -f - --record

The deployment description shows labels and selectors to have a mismatch.

Name:                   gocd-agent-jdk8
Namespace:              apex
CreationTimestamp:      Thu, 14 Apr 2016 21:07:45 +0200
Labels:                 app=gocd-agent-jdk8,release=v201604142107
Selector:               app=gocd-agent-jdk8,release=v201604151548
Replicas:               1 updated | 1 total | 1 available | 0 unavailable
StrategyType:           Recreate
MinReadySeconds:        0
OldReplicaSets:         <none>
NewReplicaSet:          gocd-agent-jdk8-70801407 (1/1 replicas created)
Events:
  FirstSeen     LastSeen        Count   From                            SubobjectPath   Type            Reason                  Message
  ---------     --------        -----   ----                            -------------   --------        ------                  -------
  12m           12m             1       {deployment-controller }                        Normal          ScalingReplicaSet       Scaled up replica set gocd-agent-jdk8-70801407 to 1

And the rollout history acts like the second deployment never happened.

REVISION        CHANGE-CAUSE
1               kubectl apply -f - --record

Am I understanding the strategy Recreate incorrectly? Or is this a bug?