There seem to be a lot of sources for Viking/10th century and 14th-century-and-after spoons, and bugger all in between... I did find a rather nice silver Byzantine spoon belonging to the Department of Antiquities, Cyprus, but being silver it's likely to be a liturgical tool and not necessarily tableware; it is however a similar shape to those spoons that came before and after it (and which WERE tableware) so we'll leave it as 'this-is-as-good-as-it-gets-at-the-moment' until more evidence rears its head.
I observed that the teardrop-shaped bowls are very much the same shape as modern 'parfait' spoons, and got a couple of cheap stainless steel ones; not being a backsmith, and being able to make the spoons from scratch, I reshaped the handles on the spoons (using a bench grinder LOL) and the end result is fairly 'period' looking.
A lot of tableware of the period (if not wooden or ceramic/pottery) is pewter, and I can find pewter spoons from later (14th-15th century) periods, but not the 12th-13th century. So far. Frustrating!