In your specific case, you can do a lower_bound("foo") and then walk forwards looking for matches, until you hit something that doesn't match or reach the end of the container. I don't think there is a general way to do this lookup though.
Well, first you don't actually have to use a boost::regex, if the wildcard is simple enough, you can get away by rolling you own unary operator. I would note that Boost.Regex is one of the few part of the library which actually requires to be linked (not header-only).
As for the problem of walking the whole structure, I am sorry but there is not much one can do you here... if you don't know the searches in advances.
If you know the parameters that you would be looking for in advance, then you can create a special view of the Multi-Index container suited to perform this task with a dedicated comparator/hasher (for example, one that only takes into account the first 3 characters).
If you were hoping for more, please provide more information regarding the kind of wildcards you want to use and the circumstances.