I had the same problem.
For now, I've settled with client-side Wildcard/Regex filtering based on http://www.codeproject.com/Articles/11556/Converting-Wildcards-to-Regexes?msg=1423024#xx1423024xx - it's simple and works as expected.
I've found another discussion on this topic: http://forums.asp.net/t/1654093.aspx/2/10
This post looks promising if you use Entity Framework >= 4.0:
Use SqlFunctions.PatIndex:
http://msdn.microsoft.com/en-us/library/system.data.objects.sqlclient.sqlfunctions.patindex.aspx
Like this:
var q = EFContext.Products.Where(x => SqlFunctions.PatIndex("%CD%BLUE%", x.ProductName) > 0);
Note: this solution is for SQL-Server only, because it uses non-standard PATINDEX function.