Either i don't understand the PagedList library or there is a bug in it that causes it's strange behavior (most likely as the library is 3 years old now). My workaround is as follows which renders the @Html.PagedListPager() almost useless and i could have written my own code in the time spent till yet.
Controller action
public System.Web.Mvc.ActionResult RenderMessageListItems(int? page)
{
  ...
  System.Linq.IQueryable<Models.Message> lQuery = from m in lDBContext.Messages orderby m.CreateTimestamp select m;
  int lPageNumber = page.HasValue ? page.Value : 1;
  int lPageSize = 5;
  // note: ViewModels.MessageListItems implements IPagedList.IPagedList
  ViewModels.MessageListItems lViewModel = new ViewModels.MessageListItems(lPageNumber, lPageSize, lQuery.Count());
  lQuery = lQuery.Skip(lPageSize * (lPageNumber - 1)).Take(lPageSize);
  foreach (Models.Message lMessage in lQuery)
  {
    ViewModels.MessageListItem lMessageListItem = new ViewModels.MessageListItem();
    lMessageListItem.ID = lMessage.ID;
    lMessageListItem.Date = lMessage.Date;
    lMessageListItem.Caption = lMessage.Caption;
    lMessageListItem.Content = lMessage.Content;
    lViewModel.Add(lMessageListItem);
  }
  return Json(new {page = page, items = RenderRazorViewToString("../Shared/MessageList/Items", lViewModel)}, System.Web.Mvc.JsonRequestBehavior.AllowGet);
}
Passing the view to the Json object caused a circular reference exception on serialization, thus the call to RenderRazorViewToString(). The code of this function has been posted here: https://stackoverflow.com/a/2759898/3936440
Partial view
...
@* the following include is needed to get Html.PagedListPager() working *@
<script src="@Html.ResourceUrl("Script", "jQuery.Ajax.Unobtrusive")"></script>
<script>
  function OnPageChanged(jsonObject, textStatus, jqXHR)
  {
    @* inject new items into message list *@
    $("[name=@{@Model.Name}Items]").html(jsonObject.items);
    @* select all page buttons *@
    var $buttons = $(".pagination li");
    @* get button linked to previous page and... *@
    var $previousButton = $buttons.filter(".active");
    @* remove active indication and... *@
    $previousButton.removeClass("active");
    @* fix missing link attributes of first page button (strangely PagedListPager wont render those) *@
    if ($previousButton.index() == 0)
    {
      var previousPageNumber = $previousButton.index() + 1;
      var $previousLink = $previousButton.find("a");
      $previousLink.attr("data-ajax", true);
      $previousLink.attr("data-ajax-success", "OnPageChanged");
      $previousLink.attr("href", "@Url.Action("RenderMessageListItems")?page=" + previousPageNumber);
    }
    @* set current page button to active *@
    var $currentButton = $buttons.eq(jsonObject.page - 1);
    $currentButton.addClass("active");
  }
</script>
...
@Html.PagedListPager(
  Model.Items, 
  page => Url.Action("RenderMessageListItems", new {page}), 
  PagedListRenderOptions.EnableUnobtrusiveAjaxReplacing(
    new PagedListRenderOptions {Display = PagedListDisplayMode.IfNeeded, DisplayLinkToNextPage = PagedListDisplayMode.Never},
    new System.Web.Mvc.Ajax.AjaxOptions {OnSuccess = "OnPageChanged"}
  )
)
As you can see, the code in OnPageChanged() fixes the non-working parts of PagedListPager. Sadly i cannot use nice functions like next / previous page buttons as this isn't rendered correctly by PagedListPager either.