Since verily means truly or certainly. Can I use it where I would normally use certainly?
I certainly think that is appropriate.
I verily think that is appropriate.
If yes, are there instances where these are not interchangeable?
Verily is archaic, and nowadays used primarily as a (facetious) interjection, usually in combination with other archaic terms ( forsooth! ) and constructions. So while your example is not wrong, you'd be more likely to hear something like:
If you were to join up with a local branch of the Society for Creative Anachronism you would likely find people using it on a regular basis. Otherwise, it is probably best if you ignore this particular word, as the use of it will verily get you awkward looks.
Additionally, I do believe that's an adverb so bear that in mind as well as you use it.