This is probably why you've got stuck on 512k. In your router there should be a way to disconnect and reconnect the PPP session (your virtual connection to the ISP), without rebooting, which cuts off your connection to the exchange, which is what causes these sorts of problems.
As for USB modems, I think when you shut your PC down properly, they will disconnect "properly" from the telephone exchange before shutting down, which doesn't make it look like there's a line fault.