Is it possible that you made the reservation at a time when you held lower status? I've had a bunch of reservations made when I was red that I needed to have the status "reapplied" at check-in after I became Gold, then Plat. Unless you happen to present your velocity card at check-in, the agent would never know you were entitled to the priority tag.
Once the correct status is on the booking, I've always received priority tags when travelling VA. One exception (sort of) was with QF staff who run checkin for NZ international in Sydney when I flew with them once did not provide the priority tag (I was distracted filling in the departure card, so I forgot to prompt the agent).
For what it's worth, this seems to extend to other airlines, and can work the other way too - a work colleague who failed to requalify as QF WP has accessed the Sydney F lounge three times since falling back to Gold because his bookings were made early and his boarding pass still prints with WP status on it!
