I've never run out of relics, so this is speculation on my part, but perhaps the game did run out of relics. The game files only specify 16 specific, named relics:
Code:
<!--Relics-->
<Row Tag="LOC_GREATWORK_RELIC_1_NAME">
<Text>Ark of the Covenant</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_2_NAME">
<Text>Beard of the Evangelist</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_3_NAME">
<Text>Blood of the Martyr</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_4_NAME">
<Text>Book of Thoth</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_5_NAME">
<Text>Footprint of the Apostle</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_6_NAME">
<Text>Grass Cutting Sword</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_7_NAME">
<Text>Holy Grail</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_8_NAME">
<Text>Philosopher's Stone</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_9_NAME">
<Text>Robes of the Guru</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_10_NAME">
<Text>Saint Aubert's Skull</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_11_NAME">
<Text>Sandals of the Prophet</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_12_NAME">
<Text>Shroud of Turin</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_13_NAME">
<Text>Silk Texts</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_14_NAME">
<Text>Splinter of the True Cross</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_15_NAME">
<Text>Stone of Scone</Text>
</Row>
<Row Tag="LOC_GREATWORK_RELIC_16_NAME">
<Text>Tooth of the Prophet</Text>
</Row>
Note: I also posted these code snippets in your Bug Reports thread.
You could check this by counting the number of relics you already have and then checking the trade screens of the other AI civs to see what relics might be available for purchase. If they all add up to 16 total relics, that may be the problem.