One possibility might be that he was not 'crew' in the sense of a merchant seaman, which would have required seaman's credentials, but working in service to one of the cabin passengers.
See this page at the Gjenvick-Gjønvik Archives, which has many examples of the different forms of passenger tickets from the steamship companies. One of the tickets shown on this page is the Immigrant Passage Contract - Sweden to New York, Cunard Line Campania 1897. The description reads:
Steamship passage contract for a 25 year-old Swedish servant,
immigrating to America from Gothenburg, Sweden on 7 April 1897.
This particular contract seems to be about an employer sending for someone who was destined to be working in his employment in America; I discovered it because the passenger came from Sweden. But it reminded me that in my own research, I have instances where there are passengers traveling on the ordinary passenger list along with their (personal) servant. If someone agreed to work as a personal servant in exchange for the price of the ticket, that might come down in a family story as having 'worked their passage'.
In order to get into the country, immigrants had to show that they had enough means to support themselves once they got here, and many communities have a pattern where people from a town come over in waves. The same thing still happens today, where immigrants come to US and establish a business (e.g. a restaurant) and then sponsor others from their extended families or their circle of friends by promising them employment in the business.
In the particular case I'm thinking of, the passenger and her servant are both from the same village. Listing the newer immigrant as a servant may have been a social pretense, with the married woman, who had already been established in the United States, acting as the single woman's sponsor, and the single girl serving as the married woman's companion.
Stewards who served the cabin passengers as their regular occupation -- employed by the steamship company -- are usually listed on the lists of crew; I don't think they would have been ticketed in the same way as a passenger. I suspect they would have been required to have some kind of credential, but they would not have the same kind of licensing required for the able seaman. See Wikipedia: Merchant Mariner's Document for the different types of modern-day US credentials, and the resources below for guides to historical research.
One important thing to remember is that many of the roadblocks we encounter in our search for records about our families are self-created. Try not to make too many assumptions. If we are too quick to rule out different possibilities we can miss important clues.