Ok, while you're working with support team I'll provide you with a few hints:
We use a dedup NAS share (storeonce) that is using a physical gateway server.
In such case FLR may take a long time, indeed. First, dedupe appliance is not the best choice for primary backup location as every time you want to restore the backup file has to be rehydrated which will take time.
Second, in order to construct a directory tree Veeam pulls metadata from the backup. You can speed up the retrieval process if you install console as close to your repository as possible (on your gateway server, for example)
Third, the same applies to your mount server - please make sure that it is installed on your gateway server or somewhere close to it.