Sometimes WordPress is unable to handle it's own permalinks properly because of cron or other stuff malfunctioning. To get permalinks properly working, often the only thing need to do is to rebuild them. If you encounter such problems from time to time, then the Permafrost plugin might be of use for you. It does rebuild permalinks permanently. So you do not need to take care of that any longer.
If a cron job caches the wrong data for a request, the first request to that data might not rebuild the permalinks fast enough to have the correct data returned. Instead the wrong data will be returned. The next request will return the correct data again.
This can be server centric, e.g. if a failover node is caching data instead of returning fresh.
Version 0.4 has been released to address this issue. Now, before the first rewrite is done in a request, the permalinks will be rebuild.
Additionally, this might be usefull:
$wp_rewrite->flush_rules();