Hmmm... I had a reply node here and it seems to have been erased when I replied to ask below in the same thread. Very strange.

Anyway, the gist of it was that you can use the table structure you suggested or serialize the whole result data structure into a blob column using Storable.

Also, make if your search criteria are in a hash make sure you sort them before you use them as the result key. Hashes can return their keys in a different order, even when the keys are identical.