On the theory that names are most useful from the client's perspective, and not the service's, how do these differ? If the client doesn't need to know whether the Foo it is requesting from the service is potentially created on-the-fly, then getFoo() is a perfectly reasonable name. To use a name like getOrCreateFoo() can reveal to the client aspects of the service that are none of the client's business.

In cases where a client does legitimately need to make a distinction between whether the service already has a Foo, naming gets problematic. Assuming that the service has getFoo() and newFoo() functions, then getOrCreateFoo() is really behavior that a client could synthesize, but which the service is absorbing as a convenience to its clients. In these cases, I've tended toward a scheme of findFoo() and getFoo(), where the former means "give me one if you've got it" and the latter means "give me one". In both cases, though, a client needs to check for none. Even in the case where a new object is going to be created on the fly, things can happen, and the burden of verifying is always on the client.

The problem of a service absorbing convenience functions into its API is a tricky one. On one hand it prevents duplication of code in clients, while on the other hand it introduces bloat into the API.