Diagnosing a maintenance plan that's ballooned in execution time
Question you asked is a very generic one and people working with database have this challenge all the time.  There is no one thing you can do will give you the answer right away.  Your case is more difficult than others as your databases are hosted by third party.

Troubleshooting long running process is a science and art at the same time. Everybody has their own way and it is not unique. 

First you want to make sure your reorganize process still doing the same work.  Which is not easy in this case because few factors:


Number of index.
Size of each index.
Fragmentation level of each index.


Once you check that out and confident that the amount of work is same, you can use method called ‘waits and queues’ to find out why the duration increased? 

A SQL server process can be in three states.  Running, Runnable and Suspended.  I suggest you read this more here.  There is nice method for capturing wait stats for one single operation.

Once you know what resources your process was waiting for and how long (during the whole duration) the waits were, you should be able to quantify the run time. You can be blocked but underneath that is also a wait because some other process is holding the resource that you need.

As you are in a hosting environment and if you have baseline number of your hardware you should check those out too, to make sure nothing changed there. I understand you did check with them but I suggest you confirm what they are saying. 

Few things to check:


storage performance 
Network