Okay, so after working on this issue for one lovely hour I did find a workaround until I can figure out why the previous page ect is not showing. I was able to find this section of edit.php:
wp("what_to_show=posts$post_status_q&posts_per_page=500&order=$order&orderby=$orderby");
The original setting of posts_per_page was 15. I changed it to 500 so that I see all posts.
I was also able to find this part in edit.php:
<div class="navigation">
<div class="alignleft"><?php next_posts_link(__('« Previous Entries')) ?></div>
<div class="alignright"><?php previous_posts_link(__('Next Entries »')) ?></div>
</div>
Which looks like it should display the navigation links. For some reason it doesn't. It does look like it tries though, because there are two blank lines at the bottom of the post list, there is just nothing in them.