Ответ на этот вопрос упирается в произнесённое слово "государство", т.к. любые теоретические построения должны опираться на устойчивую терминологию, а с ней-то как раз не всё ладно.
Когда мы говорим о государстве в истории, нужно разграничивать два уровня проблемы: государство как метафизическое понятие, не привязанное к конкретной эпохе и существующее вне времени, и государство как исторически обусловленное представление об устройстве и организации сообществ людей, существующее на разных этапах развития человечества.
Оба мнения имеют свои pro et contrae. Используя слово "государство" терминологически, то есть безотносительно лексики источников, мы сможем описать общества более "научно", дать более строгие определения и ответы. Один старший коллега из ИВИ РАН как-то в споре после своего доклада о деятельности норвежского конунга Харальда Прекрасноволосого даже сказал: если мы отказывается использовать этот термин, то мы просто остаёмся без инструмента описания исторической реальности; факт, что он не существует в тех или иных источниках, не означает, что таковая реалия не существовала в действительности. С другой стороны, многие исследователи обращают внимание на семантику этой лексемы и её реальное употребление в исторических источниках. Так, известный историк понятий Кв. Скиннер отдельно фокусирует внимание на происхождении слов, обозначающих "государство", в основных европейских языках. В частности, Скиннер справедливо замечает, что если в западноевропейских языках они восходят к латинскому status (т.е. положение или состояние), то русский термин исторически связан со словом "господство" (библиография Скиннера огромна, из доступного сошлюсь на The State : пер. с англ. / Квентин Скиннер // Понятие государства в четырех языках : Сборник статей / ред. О.В. Хархордин . – СПб. : Летний сад (СПб), 2002).
Есть и другие работы на эту тему. Например, сборник Исторические понятия и политические идеи в России XVI-XX века(СПб., 2006), где в частности есть статья Р.Козеллека «Социальная история и история понятий», характеризующая роль «истории понятий» и вслед за ней статья М.М. Крома (ЕУСПб) «Рождение "государства" : из истории московского политического дискурса XVI века». Более популярно и без акцента на историю можно почитать так же тут strana-oz.ru (за ссылки благодарю доцента кафедры исторической информатики исторического факультета МГУ А.Ю. Володина).
Эти наблюдения выводят нас на новый уровень проблемы: а эти слова вообще описывают одни и те же реалии или разные? Обратите внимание, например, что в русском языке США делятся на штаты, а не государства, но в английском они все по-прежнему states. И более того, когда мы сегодня пытаемся разобраться в ней, используя современные доступные нам языковые средства, не загоняем ли мы себя в ловушку, не обращая внимания на коннотации? Два простых примера из реальной практики:
Тем не менее, существует теория т.н. "раннего государства", разработанная в 1978 г. Х. М. Классеном и П. Скальником (Claessen, H. J. M., and Skalník, P. The Early State: Theories and Hypotheses. The Hague: Mouton). Она чем-то похожа на концепцию "дофеодального периода" А.И.Неусыхина (Неусыхин А.И. Дофеодальный период как переходная стадия развития от родоплеменного строя к феодальному (на материале истории Западной Европы раннего средневековья) // Проблемы истории докапиталистических обществ / под ред. Л. В. Даниловой. — М., 1968. — С. 596—617). В рамках этой теории Владимиром было создано раннее государство, но лично я больше практик, чем теоретик. По той же логике современная Владимиру англо-саксонская Англия — тоже раннее государство, но при этом оно гораздо сложнее устроено, более тонко управляется и заметно глубже социально стратифицировано, хотя вроде бы описывается тем же термином.
В чем у серьёзных историков нет сомнений, так это в наивности возведения нынешнего российского государства к политии князя Владимира рубежа тысячелетий.