I've upgraded on the day with VS a few times both for cash and miles. Miles upgrade rates are published and can be good value if you want a good night's sleep flying east. On the day you have a reasonable chance of moving forward if premium seats are unsold. Go to ticketing first not regular check-in: if you are successful you won't need to queue at economy. Also try upgrading via the call centre - that worked for me after I'd checked in at MCO even when the check-in agent told me it was impossible (although I had to get my boarding pass reissued). There was never a case of negotiation on price - the rate is the rate. Never tried upgrading a long time in advance so I can't comment on that.