If I start at Winhost Basic ($4.95/month) can I then upgrade to Winhost Max or Winhost Ultimate without extra fees or hassles? Would installed sites remain where there are or would they need to be reinstalled?
Yes. The sites would remain. The changes should be immediate, but the status in the Control Panel won't be updated until 24 hours has passed.
