I initially thought that the issue here has been encountered before at: http://forums.arcgis.com/threads/4525-spatial-domains-are-inconsistent-between-tools
and so suggested to try creating a new features class with the same schema and an explicit & larger domain (http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Defining_feature_class_properties/002200000002000000/), and then use this as the first input dataset to Merge.
However, having had the opportunity to try working with the actual data, my recommendation is to use Append rather than Merge, and to do the following (which I was able to do successfully):
Create a new empty feature class (I called it AppendFC) of type Point (same as the feature classes to be merged), Coordinate System GCS_WGS_1984 (same as the feature classes to be merged) and let everything else default until you get to the last panel when you use Import (from any one of the existing feature classes to get the fields to match).
Open the Append tool from the Management toolbox and use it with the five feature classes that need to be merged as the Input Datasets and the new feature class (AppendFC) as the Target Dataset. Be sure to leave Schema Type set to TEST.
On the test data sent it took just 4 seconds to Append and I believe the result is the same as what was desired from Merge. The difference is that because Append can append/merge into an existing (empty) feature class you are able to create it with the spatial domain, etc defaulting which makes it cover a much larger geographic extent than the input feature classes - but still keep the same schema.