It sounds like you have a DLL built with an older version of the C-runtime which isn't compatible with Metro style apps. If you use the C runtime from Visual Studio 11 then you should be fine.
I confirmed that using strstr in a VS11 compiled Metro style app passes certification.
--Rob