Actually, I'm going to expose myself to a lot of flame here and say that the traditional Roman state was weak because political power was vested in the generals. The bureaucracy was very weak for most of the empire's history because it was effectively a military dictatorship. Claudius may have had his public slaves but there was little standing bureaucracy outside the church and the army. Governorships were rotating, prone to corruption and purely political appointments made by military strongmen.
Now obviously Byzantine politics was complicated-it was, after all, rather Byzantine. However I'm saying that it's that complication which made the system so weak; Gibbon said it was the church which weakened the empire hugely and I agree with him; so do you I think, because it added a whole new layer of complexity to the political system.
As for the civil service keeping soldiers paid, I believe it was the generals who did that, in fact I believe that's what caused a lot of problems in the first place.
Elfine: your statement that the Byzantine Empire was the strongest state in Europe is self-fulfilling because by your definition it was the only state in Europe, i.e. a polity which didn't depend on one individual (like say Charlemagne) or on feudal ties of loyalty (like say the HRE) to survive. I'm saying that if you compare it to states similar to it in organization, like say early modern empires or Middle Eastern states of the period, it was very backwards and anachronistic.