Could you activate debugging for the VCS queries and check what is executed? Set log category org.nuxeo.ecm.core.storage.sql.jdbc to TRACE.

2012-11-14 22:09:07,091 TRACE org.nuxeo.ecm.core.storage.sql.jdbc.JDBCLogger SQL: SELECT "C1" FROM (SELECT "hierarchy"."id" AS "C1", "F2"."title" AS "C2" FROM "hierarchy" JOIN "fulltext" ON "fulltext"."id" = "hierarchy"."id" LEFT JOIN "misc" "F1" ON "hierarchy"."id" = "F1"."id" LEFT JOIN "dublincore" "F2" ON "hierarchy"."id" = "F2"."id", TO_TSQUERY('english', '(data & migration)') "nxquery" WHERE (("hierarchy"."primarytype" IN ('SectionRoot', 'Workspace', 'RelationSearch', 'BlogSite', 'ManagementRoot', 'Tag', 'AdministrativeStatusContainer', 'search_results', 'Thread', 'Space', 'TemplateRoot', 'Domain', 'WorkspaceRoot', 'Comment', 'QueryNav', 'TaskList', 'WebPage', 'WCOpenSocial', 'TaskLists', 'MailMessage', 'Forum', 'ContextualLink', 'PictureBook', 'Unit', 'TaskRoot', 'Post', 'WCHtml', 'AdministrativeStatus', 'Picture', 'UserWorkspacesRoot', 'Document', 'Folder', 'FacetedSearch', 'WCPicture', 'File', 'WebSite', 'FacetedSearchDefault', 'AdvancedSearch', 'Gadget', 'Note', 'TaskDoc', 'HiddenFolder', 'Section', 'UserProfile', 'MailFolder', 'OrderedFolder', 'BasicAuditSearch', 'CommentRoot', 'BlogPost')) AND ((nxquery @@ NX_TO_TSVECTOR("fulltext"."fulltext"))) AND ("hierarchy"."primarytype" IN ('SectionRoot', 'Workspace', 'RelationSearch', 'BlogSite', 'Thread', 'TemplateRoot', 'Domain', 'WorkspaceRoot', 'QueryNav', 'WebPage', 'MailMessage', 'Forum', 'PictureBook', 'ContextualLink', 'Picture', 'Relation', 'Document', 'Folder', 'FacetedSearch', 'File', 'AdvancedSearch', 'FacetedSearchDefault', 'WebSite', 'Note', 'Section', 'Root', 'MailFolder', 'OrderedFolder', 'BasicAuditSearch', 'BlogPost')) AND ("hierarchy"."primarytype" IN ('SectionRoot', 'Workspace', 'RelationSearch', 'PublicationRelation', 'BlogSite', 'Tag', 'ManagementRoot', 'AdministrativeStatusContainer', 'Tagging', 'Thread', 'CommentRelation', 'search_results', 'Space', 'TemplateRoot', 'Domain', 'WorkspaceRoot', 'Comment', 'QueryNav', 'TaskList', 'DefaultRelation', 'WebPage', 'WCOpenSocial', 'TaskLists', 'MailMessage', 'Forum', 'PictureBook', 'ContextualLink', 'Unit', 'TaskRoot', 'WCHtml', 'Post', 'AdministrativeStatus', 'UserWorkspacesRoot', 'Picture', 'Relation', 'Document', 'Folder', 'WCPicture', 'File', 'AdvancedSearch', 'WebSite', 'Note', 'Gadget', 'TaskDoc', 'HiddenFolder', 'Section', 'Root', 'UserProfile', 'MailFolder', 'OrderedFolder', 'CommentRoot', 'BasicAuditSearch', 'BlogPost') AND (NOT(ARRAY['HiddenInFacetedSearch'] <@ "hierarchy"."mixintypes") OR "hierarchy"."mixintypes" IS NULL)) AND ("hierarchy"."isversion" IS NULL) AND ("F1"."lifecyclestate" <> 'deleted')) UNION ALL SELECT "H"."id" AS "C1", "F2"."title" AS "C2" FROM "hierarchy" "H" JOIN "proxies" ON "H"."id" = "proxies"."id" JOIN "hierarchy" ON "proxies"."targetid" = "hierarchy"."id" JOIN "fulltext" ON "fulltext"."id" = "hierarchy"."id" LEFT JOIN "misc" "F1" ON "hierarchy"."id" = "F1"."id" LEFT JOIN "dublincore" "F2" ON "hierarchy"."id" = "F2"."id", TO_TSQUERY('english', '(data & migration)') "nxquery" WHERE (("hierarchy"."primarytype" IN ('SectionRoot', 'Workspace', 'RelationSearch', 'BlogSite', 'ManagementRoot', 'Tag', 'AdministrativeStatusContainer', 'search_results', 'Thread', 'Space', 'TemplateRoot', 'Domain', 'WorkspaceRoot', 'Comment', 'QueryNav', 'TaskList', 'WebPage', 'WCOpenSocial', 'TaskLists', 'MailMessage', 'Forum', 'ContextualLink', 'PictureBook', 'Unit', 'TaskRoot', 'Post', 'WCHtml', 'AdministrativeStatus', 'Picture', 'UserWorkspacesRoot', 'Document', 'Folder', 'FacetedSearch', 'WCPicture', 'File', 'WebSite', 'FacetedSearchDefault', 'AdvancedSearch', 'Gadget', 'Note', 'TaskDoc', 'HiddenFolder', 'Section', 'UserProfile', 'MailFolder', 'OrderedFolder', 'BasicAuditSearch', 'CommentRoot', 'BlogPost')) AND ((nxquery @@ NX_TO_TSVECTOR("fulltext"."fulltext"))) AND ("hierarchy"."primarytype" IN ('SectionRoot', 'Workspace', 'RelationSearch', 'BlogSite', 'Thread', 'TemplateRoot', 'Domain', 'WorkspaceRoot', 'QueryNav', 'WebPage', 'MailMessage', 'Forum', 'PictureBook', 'ContextualLink', 'Picture', 'Relation', 'Document', 'Folder', 'FacetedSearch', 'File', 'AdvancedSearch', 'FacetedSearchDefault', 'WebSite', 'Note', 'Section', 'Root', 'MailFolder', 'OrderedFolder', 'BasicAuditSearch', 'BlogPost')) AND ("hierarchy"."primarytype" IN ('SectionRoot', 'Workspace', 'RelationSearch', 'PublicationRelation', 'BlogSite', 'Tag', 'ManagementRoot', 'AdministrativeStatusContainer', 'Tagging', 'Thread', 'CommentRelation', 'search_results', 'Space', 'TemplateRoot', 'Domain', 'WorkspaceRoot', 'Comment', 'QueryNav', 'TaskList', 'DefaultRelation', 'WebPage', 'WCOpenSocial', 'TaskLists', 'MailMessage', 'Forum', 'PictureBook', 'ContextualLink', 'Unit', 'TaskRoot', 'WCHtml', 'Post', 'AdministrativeStatus', 'UserWorkspacesRoot', 'Picture', 'Relation', 'Document', 'Folder', 'WCPicture', 'File', 'AdvancedSearch', 'WebSite', 'Note', 'Gadget', 'TaskDoc', 'HiddenFolder', 'Section', 'Root', 'UserProfile', 'MailFolder', 'OrderedFolder', 'CommentRoot', 'BasicAuditSearch', 'BlogPost') AND (NOT(ARRAY['HiddenInFacetedSearch'] <@ "hierarchy"."mixintypes") OR "hierarchy"."mixintypes" IS NULL)) AND ("H"."isversion" IS NULL) AND ("F1"."lifecyclestate" <> 'deleted'))) AS "T" ORDER BY "_C2" – LIMIT 20 OFFSET 0 – COUNT TOTAL

(the query looks the same for both simple and phrase based searching)

The logged query is the execution of just data migration, not "data migration" with quotes, because if it was the query would contain something like:

_nxquery @@ NX_TO_TSVECTOR("fulltext"."fulltext") AND "fulltext"."fulltext" LIKE '% data migration %'

So something strips your double quotes. It may have been a bug in Nuxeo 5.5, I don't remember. Could you check with Nuxeo 5.6 please?