Even if work is paying for it, you may be able to tell your travel agent exactly what flight and fare class to book. We have to go through a specific travel agent with my work. The policy is that we have to book the cheapest ticket, or get approval from my manager if it is higher. If it was higher, I just paid the difference on my expense report (paid the company the difference). However, when the ticket was only about $50 more for a higher fare class, they booked it for me without getting the approval.

Being very friendly with the agent of course helps, as well as explaining what I am trying to accomplish (i.e. travel so much for the company, and it's nice to get free upgrades for a little more comfort but I need the elite status to have that chance, etc.)