YARPP initially did not work for me. It showed no related posts at all. Some forum posts suggested that several issues may be related to character encoding issues.
YARPP creates 2 tables if they don't exist: $wpdb->prefix}yarpp_related_cache and $wpdb->prefix}yarpp_keyword_cache
The plugin does not work if the default charset and collate of your database do not match with the hardcoded values in includes.php (utf8 and utf8_unicode_ci)
YARPP started to work after I manually changed the collate of the yarpp cache tables to the default collate of the database.
This may be the solution for several people on the forum who found that the plugin stopped working for them after they to another server.
Mitcho, you may want to change the generation of the tables so that you don't make assumptions about the charset and collate.