Hi,
deleting URLs does not have any effect, because as I already wrote above, JoomSEF DOES NOT care about what your domain is. It only works with PATH.
As regards the domain change, this may be dependant on Joomla version - you do not write what it is.
Anyway, Joomla 1.5 detects the base URL automatically, so you just need to make sure that all alternative URLs are redirected to 1 main URL which Joomla will then use. (alternativelly, you can override it by using the live_site variable in configuration.php)
In Joomla 1.0, this is set manually by live_site only, there is no auto-detection.