What about a rotunda?

http://www.myfonts.com/search/rotunda/fonts/

My Espinosa Nova Rotunda:

http://www.myfonts.com/fonts/estudio-ch/espinosa-nova/rotunda-bold-alt/

How subtle a hint are you looking for? You may be thinking of something like Cloister Lightface (another version here) (and still another) or (less subtle) Jenson Oldstyle instead of a rotunda, although rotundas are highly legible.

Rotunda is good, but maybe still a bit too medieval.

I guess I am looking for Medieval with a bit of modern too.

Cloister is quite nice - Medieval. I do like the 'e' and the 'k'.

Jenson could be another possibility.

A typeface with a bit more Medieval to it would be great. Something in between Rutunda and Cloister.

Adobe Jenson? http://www.myfonts.com/fonts/adobe/jenson/
Golden Type? http://www.myfonts.com/fonts/itc/golden-type/

Adobe Jenson? http://www.myfonts.com/fonts/adobe/jenson/
Golden Type? http://www.myfonts.com/fonts/itc/golden-type/

Hmm. I'm going to point you at Manfred Klein's site:

http://manfred-klein.ina-mar.com/
http://moorstation.org/typoasis/designers/klein/index.htm

Or you might want something like Kingthings Petrock or Perry Gothic.

Ah, here's the type designer I was really thinking of:

http://moorstation.org/typoasis/designers/steffmann/

He specializes in typefaces that might be of interest, for example there is this rotunda:

http://moorstation.org/typoasis/designers/steffmann/samples/t/typo_rotunda.htm

And from Typodermic Fonts, there's Goodfish and Vinque.

Goudy Medieval.

How about the "country specific" versions of Andron?

Wow, Andron is really nice!

There are various understated Carolingian faces that might fit. Alcuin, for example.