Issue 1:
It seems that if a pod doesn't fit on any node, we are trying to schedule it without any backoff.

As an example see those logs from our big cluster:

I0516 11:17:25.112607 5 event.go:216] Event(api.ObjectReference{Kind:"Pod", Namespace:"kube-system", Name:"heapster-v1.1.0.beta1-3233973386-krr39", UID:"75476330-1b54-11e6-a7f5-42010af00002", APIVersion:"v1", ResourceVersion:"229057", FieldPath:""}): type: 'Warning' reason: 'FailedScheduling' pod (heapster-v1.1.0.beta1-3233973386-krr39) failed to fit in any node
...
I0516 11:17:25.213493 5 event.go:216] Event(api.ObjectReference{Kind:"Pod", Namespace:"kube-system", Name:"heapster-v1.1.0.beta1-3233973386-krr39", UID:"75476330-1b54-11e6-a7f5-42010af00002", APIVersion:"v1", ResourceVersion:"229058", FieldPath:""}): type: 'Warning' reason: 'FailedScheduling' pod (heapster-v1.1.0.beta1-3233973386-krr39) failed to fit in any node
...
I0516 11:17:25.290314 5 event.go:216] Event(api.ObjectReference{Kind:"Pod", Namespace:"kube-system", Name:"heapster-v1.1.0.beta1-3233973386-krr39", UID:"75476330-1b54-11e6-a7f5-42010af00002", APIVersion:"v1", ResourceVersion:"229162", FieldPath:""}): type: 'Warning' reason: 'FailedScheduling' pod (heapster-v1.1.0.beta1-3233973386-krr39) failed to fit in any node
...
I0516 11:17:25.351509 5 event.go:216] Event(api.ObjectReference{Kind:"Pod", Namespace:"kube-system", Name:"heapster-v1.1.0.beta1-3233973386-krr39", UID:"75476330-1b54-11e6-a7f5-42010af00002", APIVersion:"v1", ResourceVersion:"229171", FieldPath:""}): type: 'Warning' reason: 'FailedScheduling' pod (heapster-v1.1.0.beta1-3233973386-krr39) failed to fit in any node

So it seems we are trying to schedule as often as possible, which is definitely a bug.

@davidopp @gmarek @kubernetes/sig-scheduling

Issue 2:
Is this a request for help? (If yes, you should use our troubleshooting guide and community support channels, see http://kubernetes.io/docs/troubleshooting/.): No

What keywords did you search in Kubernetes issues before filing this one? (If you have found any duplicates, you should instead reply there.): namespace terminating 1.4.6

Is this a BUG REPORT or FEATURE REQUEST? (choose one): Bug report

Kubernetes version (use kubectl version):

Client Version: version.Info{Major:"1", Minor:"3", GitVersion:"v1.3.4", GitCommit:"dd6b458ef8dbf24aff55795baa68f83383c9b3a9", GitTreeState:"clean", BuildDate:"2016-08-01T16:45:16Z", GoVersion:"go1.6.2", Compiler:"gc", Platform:"linux/amd64"}
Server Version: version.Info{Major:"1", Minor:"4", GitVersion:"v1.4.6", GitCommit:"e569a27d02001e343cb68086bc06d47804f62af6", GitTreeState:"clean", BuildDate:"2016-11-12T05:16:27Z", GoVersion:"go1.6.3", Compiler:"gc", Platform:"linux/amd64"}

Environment:

Cloud provider or hardware configuration: GKE

OS (e.g. from /etc/os-release): Ubuntu 16.04

Kernel (e.g. uname -a): 4.4.0-47-generic

Install tools: N.A

Others: N.A

What happened:

After upgrading our cluster from 1.4.0 to 1.4.6, when deleting a namespace it gets stuck in Terminating.

What you expected to happen:

Have the namespace deleted.

How to reproduce it (as minimally and precisely as possible):

Upgrade from 1.4.0 to 1.4.6 and delete a namespace.

Anything else do we need to know:

I found #19317 and #37278, but one is specific to thirdpartyresources and the other one to openshift. This issue happens on all namespaces with no special finalizer or thirdpartyresource.