I removed the article IDs from the URL by editing the router.php as described here.
This works fine for the most part, but there are a few pages that display a 404 Article not found error instead of the proper page. The original URL (with the embedded article ID) still works. As far as I can tell there aren't any duplicate alias names, but I'm not ruling anything out yet.
I'm currently using Joomla 3.4.8. Any ideas?