Kibana 3 - Wildcard query with key/value pair

I have a log file that contains a message field that contains XML data in it.

message=<XML......>

I am trying to do a wildcard search within that data for a key/value pair (key="value") and I am having some issues. We don't want to index all of the data in the XML data, but there is often a case where we need to search for specific data within the XML.

I started with this:

message:*key="value"*

This will return anything that matches key or value, but not both together. So I get way more results than I want.

I tried putting it into a regex:

message:*(key)\s?=\s*("value"|'value')*

So right now the only way I have been able to come close is with something like this:

message:*value* AND message:*key*

However this will still return other entries that do not match exactly what I want. For example if the following were present it would be returned as a match

  foo=value
  key=bar

Thanks for any help.