I'm a bit puzzled by your assertion that you can't recast the sentence. The only situation I can think of in which you are free to use the punctuation and capitalization of your choice but are not free to change any of the words is when you are quoting verbatim someone's (spoken) wording.
In addition, even assuming that the sentence's punctuation in general is alterable, we haven't yet established the full range of acceptable punctuation marks, because we don't know whether the words "When in doubt, let them out. They'll be back." are some sort of official departmental wording, or whether they constitute the gist of a philosophy (as understood and rephrased by the author) that was originally stated in very different words or perhaps never explicitly stated at all. This distinction is crucial (in my view) because it determines whether using quotation marks would be accurate or potentially extremely misleading.
Suppose that the head of the department summoned the other department members and said, "We have a new philosophy here in the Kenneling Department: 'When in doubt, let them out. They'll be back.'" In that case, it would be appropriate to put quotation marks around the quoted phrase, and you could confidently handle the punctuation in a more parenthetical-friendly way. For example:
The department's philosophy—"When in doubt, let them out; they'll be back"—has not proved to be successful.
The situation is more problematic if the department has written out a statement that says something like "Our philosophy: When in doubt, let them out. They'll be back." In this case, if you can't paraphrase, you also can't change the original punctuation willy-nilly. Perhaps the best you can do under those conditions is something like this:
The department's philosophy ("When in doubt, let them out. They'll be back.") has not proved to be successful.
But there is another possibility. Suppose that the head had said something like this: "We're going to do things a little differently from now on, starting with leaving all the kennel gates open, since we believe that the kind of guests we want to encourage to take up residence here will appreciate the added freedom and won't abuse it." In that case, the author of your original example sentence is completely restating the department head's comments and characterizing them as a philosophy without conceding that he or she is doing those things. And under the circumstances, it seems to me, the most misleading thing you could do would be to put the author's version of the so-called philosophy in quotation marks, as though attributing it verbatim to the department head.
To be fair to the department head, you would have to slip some kind of explicit acknowledgment that the wording of the philosophy is not his or hers. Something like this:
The department's philosophy—which amounts to saying "When in doubt, let them out; they'll be back"—has not proved to be successful.
If I were forbidden to alter anything but punctuation and capitalization, and yet I knew that the attributed philosophy wasn't anything that the department head had ever spoken or written, I think that I would try to present it in the visual equivalent of a monotone:
The department's philosophy—when in doubt, let them out; they'll be back—has not proved to be successful.
The absence of capitalization and end punctuation in the statement of the philosophy does as much as such visual elements of style can to avoid making the wording look like a quotation.