Императрица Екатерина считала Волынского преданным себе человеком, помнила его короткие отношения к Виллиму, а потому одним из первых её распоряжений было снятие с бывшего астраханского губернатора опалы. Не далее как месяцев через пять Артемий Петрович получил новое назначение: быть казанским губернатором и заведующим калмыцкими делами; вместе с тем сложен был с него штраф и последовало распоряжение о возвращении удержанного жалования.
В иерархическом отношении это назначение не было шагом вперёд, но оно приближало к административному центру, ко двору, к которому стремились тогда все искавшие милостей. По принятому обыкновению, в Казань назначались губернаторами всегда из более родовитых фамилий, более близких ко двору и более влиятельных.
Новое назначение ещё более возбудило прежних врагов Волынского. Императрице не раз докучали докладами, в особенности генерал-прокурор Ягужинский, о неудобстве совместного управления обширной губернией и заведовании калмыцкими делами, о неизбежных, вследствие этого, упущениях и необходимости подчинения калмыцких дел надзору главного начальника войск, находившихся на Волге и на Дону, фельдмаршала князя Голицына. Несмотря на представления тайного совета, императрица отстаивала Артемия Петровича, оставила его при обеих должностях, а для устранения неудобства совместного заведывания делами в разных местностях велела назначить в помощь ему вице-губернатора, который управлял бы губерниею во время его отсутствия.
Враги, однако же, не унимались, а, напротив, становились всё настойчивее и упорнее. По их настояниям военная коллегия передала Артемия Петровича суду за дерзкое обращение с мичманом Мещерским, удержанное жалованье не выдавалось, а все его распоряжения по калмыцким делам представлялись с самой чёрной стороны. Чувствуя на себе постоянные уколы врагов, Волынский, почти тотчас же по приезде в Казань, стал проситься в отпуск в Петербург, для личных объяснений с императрицею. Этот отпуск он получил в июне 1726 года.
Личные объяснения с императрицей увенчались полным успехом: Артемия Петровича наградили чином генерал-майора и оставили при обеих должностях, но ненадолго. Через несколько же месяцев, в начале 1727 года, он был удалён от этих должностей, вследствие каких именно причин – неизвестно, можно только догадываться, что этой немилостью он был обязан донесениям фельдмаршала князя Михаила Михайловича Голицына по калмыцким делам.
Кончина императрицы Екатерины и воцарение Петра II застали Артемия Петровича в Петербурге, в звании шталмейстера, но без всякого официального значения. Правда, недоброжелатели, стараясь оттереть его от двора, назначали ему командировки то в Голландию, то в Персию и Украину, но Артемий Петрович не торопился исполнением поручений и оставался в Петербурге, укрепляясь связями с милостивцами. И милостивцы ему помогли: в мае 1728 года он был снова назначен казанским губернатором, без заведования, впрочем, калмыцкими делами.
Казань в то время могла назваться безопасным притоном всякого рода преступников, воров и разбойников. Целые шайки беглых и беспаспортных скитальцев свободно прогуливали там свои легко приобретённые деньги в кабаках и домах разгульных женщин.
Артемий Петрович ревностно принялся за дело и скоро энергическими мерами очистил город и окрестные слободы от шаек бродяг; притоны и дома разгульных женщин закрылись, а постоянными караулами и обходами полицейских команд водворились тишина и безопасность.
Власть губернатора в то время имела иной, широкий характер. Ещё императрица Екатерина, находя введённые покойным мужем областные коллегиальные учреждения тягостными для народа, уничтожила их почти все, возложив их права по управлению и суду единолично на губернаторов.