You might want to add the Medium / Partial Trust requirement in a visible place in your documentation, since developers typically develop in full trust, while hosting companies usuaully do not allow this.
It will be very frustrating to invest several months in development, only to find out the solution can't be hosted on production server.
Also, you can contact hosting companies and ask them if they provide full trust hosting plans. I've read in the CSLA forums about full trust and found a list of hosting providers, that may provide that (but still, this needs to be double checked with the hosting provider).
Here are a list of hosting sites that may provide full trust: