it's possible.. all u need is to designate a cisco router as a frame relay switch, find a way to connect it to the other, which is back to back serial in most cases, and u have a frame relay cloud..
long distance frame relay is where u typically need to use a telco.. with a frame relay switch...
good luck..