What are the rules for standard library containers and incomplete types?

std::deque<S> *p;   // seems to be UB like the previous case, 
                   // but is it ok if p is not used till S is defined?

That's actually the interesting bit here. Yes, instantiating that container with an incomplete type is not allowed, there is no provision for it. But the question becomes whether or not it's really instantiated. It doesn't have to be, according to the core language.

[temp.inst]

1 Unless a class template specialization has been explicitly instantiated or explicitly specialized, the class template specialization is implicitly instantiated when the specialization is referenced in a context that requires a completely-defined object type or when the completeness of the class type affects the semantics of the program.

A pointer to a type doesn't require the type to be complete. So this declaration alone is not normally enough to cause an instantiation of a class template, and so it may be premature to determine the requirement of the container is violated here.

Unless of course we take "the completeness of the class type affects the semantics of the program" to include contract violations in the standard library. An implementation could instantiate here, I suppose. I'm not aware of any implementation that does however, so this may not be the desires interpretation.

So to err on to side of caution, I'd deem this UB too.

---

std::deque<S*> p;  // not really sure about this one

This is fine. Whether or not S is complete, S* is still a complete object type. I say this because it's not included at

[basic.types]

5 A class that has been declared but not defined, an enumeration type in certain contexts ([dcl.enum]), or an array of unknown bound or of incomplete element type, is an incompletely-defined object type. Incompletely-defined object types and cv void are incomplete types ([basic.fundamental]). Objects shall not be defined to have an incomplete type.

The constraints about the completeness of S only appear when attempting to use such a pointer in an expressions that does a dereference or pointer arithmetic. But the pointer type itself is still complete. So it's a valid template argument for a container type.