Efectivamente, parece que la palabra buten por sí sola no significa nada, y hay pocos casos en el CORDE, siendo los primeros de finales del siglo XIX, como comentas. Para estos casos en cuando conviene comenzar a investigar en el fichero general, y ver qué comentan las cédulas allí presentes sobre la palabra buten.
La primera que me encuentro con datos interesantes comenta lo ya adelantado por @blonfu:
Según Belmonte, del alemán guten; según J.M. Medina, de butyrum. Se usa también en la Argentina.
Otra ficha parece identificar el término como un gitanismo. Otra como procedente de la germanía. Otra incide en su origen del alemán guten y explica que la expresión completa era de buten niquelá. Esto me resulta curioso, porque en Andalucía usamos la expresión "estar niquelado" o "niquelao" para decir que algo está perfecto ("-¿Qué tal el examen? -Niquelao."). Otra comenta que al principio se usaba casi exclusivamente para referirse a mujeres.
Encuentro otra ficha que hace referencia al Vobaculario andaluz, que explica lo mismo que la mencionada arriba sobre los dos posibles orígenes, pero añade que butyrum significa leche y miel, y que su significado es abundante, como en "fue una comida de buten".
Si juntamos todo lo anterior, el resultado (y esto ya es divagación mía) es que buten podría ser una palabra de origen andaluz, pero originada por gitanos que viajaran por Europa e incorporaran palabras extranjeras a su habla, como podría ser guten del alemán.
En todo caso, queda claro que es una palabra que se usa siempre (y en esto coinciden todas las fichas consultadas) precedida de la preposición de, consistiendo pues ambas en una locución inseparable cuyas palabras sueltas carecen de significado.
