Reading input from stdin
Architecture

stdin is usually line buffered.  So nothing is given to fgetc() until the user hits Enter.  OP code will give multiple error messages with input like "Hello 123".  Better to separate user input from input validation.  Read the line of user input with fgets() or some version of your own as fgets() does have some weaknesses.  Then validate the input.

char *input;
while ((input = my_gets()) != NULL) {
  if (valid_phrase(input)) {
    foo(input);
  } else {
    fprintf(stderr, "Invalid input\n");
  }
  free(input);
}


Concerning "I would love to get rid of the outer while loop".  That loop exists to silently consume '\n'.  If you want a loop to do that, just preceded inner loop with

int ch;
while ((ch = fgetc()) == '\n')
  ;
ungetc(ch, stdin);


char ch

The ch is not the best type.  fgetc() returns typically 257 different values [0-255] and EOF.  To properly distinguish them, save the result in an int.

// bad
char ch;
..
while (string == NULL &amp;&amp; ch != EOF) {    
while (EOF != (ch = fgetc(in_stream)) &amp;&amp; ch != '\n') {

// better
int ch;
..
while (string == NULL &amp;&amp; ch != EOF) {
  while (EOF != (ch = fgetc(in_stream)) &amp;&amp; ch != '\n') {


Same for char tmp;

realloc()

Cast not need.
Modify for out of memory to free string - not needed if code will simply exits, yet good practice to put your toys (code's pointer) away.

// string  = (char*) realloc(string, len+2);
char * new_string  = realloc(string, len+2);
if (new_string == NULL) {
  free(string);
  bail_out(EXIT_FAILURE, "Out of memory");
}
string = new_string;


Good use of of sizeof(*strings) below.  Recommend simplification.

strings = (char**) realloc(strings, (index+1)*sizeof(*strings));
strings = realloc(strings, sizeof *strings * (index+1));


size_t len

Good use of size_t to represent an array size.  Curiously code does not do  the same with int index;.  Recommend size_t index;

is...()

With using int ch, no need for cast.  Since this is a logical test, recommend using ! rather than arithmetic == 0.

// if (ch != ' ' &amp;&amp; isalpha((int)ch) == 0) {
if (ch != ' ' &amp;&amp; !isalpha(ch)) {


The following may be easier to understand - fewer negations.  (Style issue)

if (!(ch == ' ' || isalpha(ch))) {


ferror()

Nice check of if (ferror(in_stream)) 

Variable names

string, strings is as useful as calling an integer integer.  Maybe phrase, dictionary instead.

// OK
/** @brief Contains the dictionary */
static char **strings = NULL;

// Better
// comment not truly needed
static char **dictionary = NULL;


get_strings() is mis-named.  It sounds general, yet code restricts input to letters and space.  Maybe get_words()?