I was working on some custom pagination functionality for WordPress, and after much too long I found out you <em>have to flush the permalink cache</em>. Just go to Settings > Permalinks and click on “save” without making any changes. That’s it.
Check out WordPress’ great <pre>wp_rewrite</pre> class and endpoint functionality.