WP_query sorting can't sort danish letters (æ, ø, å)

Question

I am having an issue, with making a WP query sort correctly, using danish special letters (æ, ø and å in this case).

I have a loop running a query for certain post types, then returning them alphabetically, also displaying the first letter in each 'category' as the headline.

I initially had some issues with using single-byte functions, not being able to display the æ, ø and å, and I thought fixing that, would resolve this issue as well. It did not.

Here's my code for the query, including 'category headline':

$args = array( 
  'orderby'   => 'title',
  'order'     => 'ASC',
  'post_type' => 'ord',
  'posts_per_page' => -1
  );
$loop = new WP_query($args);


$mainArray = array_chunk($loop->posts, ceil(count($loop->posts) / 4)); // Array af arrays

foreach ($mainArray as $array) {
$first_letter = '';

  echo "<div class='col ordbog-column'>";
  foreach($array as $post) {
    $current_letter = mb_strtoupper(mb_substr($post->post_title,0,1));

    if($current_letter != $first_letter) {
      echo "<h3 class='letter' id='letter_$current_letter'>$current_letter</h3>";
      $first_letter = $current_letter;
    }

    $html = '<a href="'.get_permalink().'" class="ord">'.get_the_title().'</a><br/>';
    echo $html;
  }
  echo "</div>";
} 

The issue at hand is that if I run a print_r($loop), even the WP query doesn't return them in the right order, despite it being able to print the letters correctly.

I think this indicates that something should be wrong with the DB, so I changed the table collation to UTF8_general_ci (on development), to no avail.

I'm at my wits end here, how do I debug this?