The normal way to search for an item like that would be to send out request to other covenants through the Redcaps. For many services the Redcap network could actually point you to people who have provided a similar service for them.
So if you (the SG) know someone has the item and is willing to sell it (or entertain selling it) then the time would be a round trip message. One season after you send it out is reasonable for within a Tribunal with a good network (and those adjacent to them might take a season more). If you are unsure if someone has the item and is willing to sell, then the chance roll is very much YSMV. I can't help you much here since how common things are is entirely up to your Saga with little in RAW that gives you an average level.
If near the Rome Tribunal than finding someone to enchant something for you is fairly easy. Very common enchanted items (lights, Vis scales, etc) will often even have some already made that you can trade for (whether from the Redcaps or Verditius Magi). For something not with premade stock, figure message time plus enchantment time and a season per some number of Mags to cover back log (saga dependent, though I would use 2 Mags per +1 season).
If you ask the Redcaps and send a bunch of "request" messages for an enchanted item, you would have a round trip message time of 1 season to the Redcaps and within your Tribunal, with say 2 seasons to Rome. This includes not just travel time, but also their proctors reading your request and drafting a reply. The Redcaps would tell you yes or no, they can proctor or have the item for sale. Depending on your Tribunal you will get anything from no replies to a bunch depending on how many enchanters for hire there are. You will get some replies from the Rome Tribunal.
Redcap proctoring would cost however much extra you decide on, but the Redcap network would handle the details of finding and hiring the enchanter. Great for simple or common items, not so good for complex or custom items. They will most likely not proctor non-enchanted items, though would most likely be willing to sell anything they have stock of. For items of Virtue this would depend on how common they are in your game.
So if you had to go through a Rome enchanter, 2 seasons to send a request and get a reply, 2 seasons to confirm, enchantment time, plus 1 season for every 2 Mags enchanted would give you a rough total time. It will take years on average, but that is to be expected with the speed of communication and that you are dealing with producing items that takes seasons to make. Enchanters for hire will have a backlog before they get to your item.
All this is assuming your characters are doing everything by letters from their covenant. If they travel to a Tribunal then things can advance much faster, cutting out all the message time and being able to buy items that are on display.
Don't know if that all helps any.
EDIT: In my saga, at least the plant based items of virtue are reasonably common. Our primary SG rolls a Die and subtracts the Vis contained + a number from the die to find out how many the Redcap Vis bank has at a given time. I can bug him for the actual math if you want.