When I recently used an upgrade certificate received via a corporate program, I presented it at the Airport Express check in, and they called up the flight control immediately to see if it could be used. Then they reprinted my boarding pass immediately. this was about 3 hours before the flight.
I didnt get all the details from check in. I upgraded myself from Y (think i was V class) to J on a LAX-HKG a while ago. I dont remember how i got the upgrade voucher. The check in desk said that i can use it no matter what as long as there are seats in the next class up.