>while(next != string.str)
Strings cannot be compared with relational operators. Use strcmp or strncmp (or memcmp) instead:
Code:
/* Work on your naming scheme! */
if ( strcmp ( (*st)->str.str, string.str ) == 0 ) {
  /* Remove the first node */
  node = *st;
  *st = (*st)->next;
}
else {
  /* Remove everything else */
  while ( strcmp ( next->next->str.str, string.str ) != 0 )
    next = next->next;
  node = next->next;
  next->next = next->next->next;
}
Okay, now my head is spinning from all of those str's and next's. Hopefully I wasn't too disoriented to give you a correct algorithm.