I used to have issues like this then I started using a DRY config.php file. I would strongly recommend doing the same. My first config.php file was based on the one from this NetTuts article, "Apply the DRY Principle to Build Websites With ExpressionEngine 2". If you set this up right you won't need to mess with REElocate anymore.
If you do use this approach and you still have problems, clear your cache and resave the entries. If the problem STILL persists then you might need to go into the SQL manually and fix the paths and hope they don't resurface.
update
Now that I'm in the office and have a couple minutes I can share my default config file (the database.php file is the same as the one from the article).
The biggest change from the NetTuts article is the use of $_SERVER['HTTP_HOST'] instead of $_SERVER['SERVER_ADDR'] because I tend to setup the staging server as a subdomain on the clients production server. This is to ensure that PHP and MySQL setting issues are caught early on and relying on IP addresses is difficult at best when doing this. Plus it's more human readable so you know what the development, staging, and production servers are. I am also a single developer so I don't setup a local production server where multiple devs can sync their efforts. You can easily add one by duplicating one of the switch cases.
If you want to learn more about some of the other hidden config variables in this config file, or others you can add at your own discretion, I would recommend this page on devot-ee. Te EE docs cover some variables but this page documents previously undocumented one that can be very useful.
I should also note that this is by far the only DRY config.php setup around. Focus Lab LLC’s EE Master Config is a very competent setup for doing the same thing and it sits above the web root which makes it easier to find and edit. Another popular approach is NSM Config Bootstrap. To each their own. I decided to start with something basic and add to is while I learn more about what's really going on under the hood.
/* Environmental Variables
-------------------------------------------------------------------*/
switch ( $_SERVER['HTTP_HOST'] ) {
// development
case 'mysite.dev' :
$db['expressionengine']['hostname'] = "";
$db['expressionengine']['username'] = "";
$db['expressionengine']['password'] = "";
$db['expressionengine']['database'] = "";
break;
// staging
// case 'staging.mysite.com' :
// $db['expressionengine']['hostname'] = "";
// $db['expressionengine']['username'] = "";
// $db['expressionengine']['password'] = "";
// $db['expressionengine']['database'] = "";
// break;
// live
// case 'mysite.com' :
// $db['expressionengine']['hostname'] = "";
// $db['expressionengine']['username'] = "";
// $db['expressionengine']['password'] = "";
// $db['expressionengine']['database'] = "";
// break;
}
/* Universal Variables
-------------------------------------------------------------------*/
$config['app_version'] = "253";
$config['license_number'] = "1111-2222-3333-4444";
$config['debug'] = "1";
$config['install_lock'] = "";
$config['system_folder'] = "system";
$config['admin_file'] = "admin.php";
$config['doc_url'] = "http://expressionengine.com/user_guide/";
$config['is_system_on'] = "y";
$config['cookie_prefix'] = "";
$config['site_name'] = "Default EE install";
$config['allow_extensions'] = "y";
$config['enable_db_caching'] = "y";
$config['debug'] = "1";
$config['daylight_savings'] = date('I') ? 'y' : 'n'; // Autodetect DST
$config['cp_session_ttl'] = 3600; // Keep admins logged in for one hour! (in seconds)
/* General Path Settings
-------------------------------------------------------------------*/
$config['site_index'] = "";
$config['site_url'] = "http://".$_SERVER['HTTP_HOST'];
$config['server_path'] = $_SERVER['DOCUMENT_ROOT'];
// $config['cp_url'] = $config['site_url']."/".$config['system_folder']; // use if keeping system within root
$config['cp_url'] = $config['site_url']."/".$config['admin_file']; // use if moving system one level above root
/* Universal database connection settings
-------------------------------------------------------------------*/
$active_group = 'expressionengine';
$active_record = TRUE;
$db['expressionengine']['dbdriver'] = "mysql";
$db['expressionengine']['dbprefix'] = "exp_";
$db['expressionengine']['pconnect'] = FALSE;
$db['expressionengine']['swap_pre'] = "exp_";
$db['expressionengine']['db_debug'] = FALSE;
$db['expressionengine']['cache_on'] = FALSE;
$db['expressionengine']['autoinit'] = FALSE;
$db['expressionengine']['char_set'] = "utf8";
$db['expressionengine']['dbcollat'] = "utf8_general_ci";
$db['expressionengine']['cachedir'] = $config['cp_url']."/expressionengine/cache/db_cache/";
/* Member directory paths and urls
-------------------------------------------------------------------*/
$config['avatar_url'] = $config['site_url']."/images/avatars/uploads/";
$config['avatar_path'] = $config['server_path']."/images/avatars/uploads/";
$config['photo_url'] = $config['site_url']."/images/member_photos/";
$config['photo_path'] = $config['server_path']."/images/member_photos/";
$config['sig_img_url'] = $config['site_url']."/images/signature_attachments/";
$config['sig_img_path'] = $config['server_path']."/images/signature_attachments/";
$config['prv_msg_upload_path'] = $config['server_path']."/images/pm_attachments/";
/* Misc directory paths and urls
-------------------------------------------------------------------*/
$config['theme_folder_url'] = $config['site_url']."/themes/";
$config['theme_folder_path'] = $config['server_path']."/themes/";
/* File directory paths and urls
-------------------------------------------------------------------*/
// $config['upload_preferences'] = array(
// 1 => array(
// 'name' => 'name of directory',
// 'server_path' => $config['server_path']."/assets/path/to/directory/",
// 'url' => $config['site_url']."/assets/path/to/directory"
// )
// );
/* Templates Preferences
-------------------------------------------------------------------*/
// $config['save_tmpl_files'] = "y";
// $config['tmpl_file_basepath'] = $config['server_path']."/templates/";
$config['site_404'] = "404/index";
$config['strict_urls'] = "y";
$config['hidden_template_indicator'] = "_";
$config['autosave_interval_seconds'] = "99999";
$config['word_separator'] = "underscore";
// END EE config items
