Yes they do but they ultimately chose Virata's Matsya Kingdom and there is a reason.
Twelve years of exile were coming to an end and after Jayadratha tried to capture Draupadi, they left Kamyaka woods and went to Dwaitavana.
Vaisampayana said, "Having felt great affliction on account of the abduction of Krishna, king Yudhishthira of unfading glory, with his brothers, left the woods of Kamyaka and returned to the delightful and picturesque Dwaitavana abounding in trees and containing delicious fruits and roots. And the sons of Pandu with their wife Krishna began to reside there, living frugally on fruits and practising rigid vows.
One day, a brahmana's fire-sticks and churning staff were stolen by a deer.
And while those repressers of foes, the virtuous king Yudhishthira, the son of Kunti, and Bhimasena, and Arjuna, and those other sons of Pandu born of Madri, were dwelling in Dwaitavana, practising rigid vows, they underwent, for the sake of a Brahmana, great trouble, which, however, was destined to bring about their future happiness. I will tell thee all about the trouble which those foremost of Kurus underwent while living in those woods, and which in the end brought about their happiness. Do thou listen to it! Once on a time, as a deer was butting about, it chanced that the two sticks for making fire and a churning staff belonging to a Brahmana devoted to ascetic austerities, struck fast into its antlers. And, thereupon, O king, that powerful deer of exceeding fleetness with long bounds, speedily went out of the hermitage, taking those articles away. And, O foremost of Kurus, seeing those articles of his thus carried away, the Brahmana, anxious on account of his Agnihotra, quickly came before the Pandavas. And approaching without loss of time Ajatasatru seated in that forest with his brothers, the Brahmana, in great distress, spake these words, 'As a deer was butting about, it happened, O king, that my fire-sticks and churning staff which had been placed against a large tree stuck fast to its antlers. O king, that powerful deer of exceeding fleetness hath speedily gone out of the hermitage with long bounds, taking those articles away. Tracking that powerful deer, O king, by its foot-prints, do ye, ye sons of Pandu, bring back those articles of mine, so that my Agnihotra may not be stopped!'
Then, the Pandavas agreed to get the fire-sticks from the deer but it made itself invisible and eventually, after trying to get it, they got tired.
Hearing these words of the Brahmana, Yudhishthira became exceedingly concerned. And the son of Kunti taking up his bow sallied out with his brothers. And putting on their corselets and equipped with their bows, those bulls among men, intent upon serving the Brahmana, swiftly sallied out in the wake of the deer. And descrying the deer at no great distance, those mighty warriors discharged at it barbed arrows and javelins and darts, but the sons of Pandu could not pierce it by any means. And as they struggled to pursue and slay it, that powerful deer became suddenly invisible.
Then, Yudhisthira asked Nakula to climb the lake and see if there is water. He saw the water and went to the water.
Vaisampayana continued, "Then king Yudhishthira addressed Nakula saying, 'Do thou, O son of Madri, climb this tree and look around the ten points of the horizon. Do thou see whether there is water near us or such trees as grow on watery grounds! O child, these thy brothers are all fatigued and thirsty.' Thereupon saying, 'So be it,' Nakula speedily climbed up a tree, and having looked around, said unto his eldest brother, 'O king, I see many a tree that groweth by the water-side, and I hear also the cries of cranes. Therefore, without doubt, water must be somewhere here.' Hearing these words, Kunti's son Yudhishthira, firm in truth, said, 'O amiable one, go thou and fetch water in these quivers!' Saying, 'So be it,' at the command of his eldest brother Nakula quickly proceeded towards the place where there was water and soon came upon it.
Sky warned him not to drink but he drank and fell dead
And beholding a crystal lake inhabited by cranes he desired to drink of it, when he heard these words from the sky, 'O child, do not commit this rash act! This lake hath already been in my possession. Do thou, O son of Madri, first answer my questions and then drink of this water and take away (as much as thou requirest). Nakula, however, who was exceedingly thirsty, disregarding these words, drank of the cool water, and having drunk of it, dropped down dead.
Long time passed, Yudhisthira sent Sahadeva and became thirsty and drank water despite the warnings.
And, O represser of foes, seeing Nakula's delay, Yudhishthira the son of Kunti said unto Sahadeva, the heroic brother of Nakula, 'O Sahadeva, it is long since our brother, he who was born immediately before thee, hath gone from hence! Do thou, therefore, go and bring back thy uterine brother, together with water.' At this, Sahadeva, saying, 'So be it,' set out in that direction; and coming to the spot, beheld his brother lying dead on the ground. And afflicted at the death of his brother, and suffering severely from thirst, he advanced towards the water, when these words were heard by him, 'O child, do not commit this rash act! This lake hath already been in my possession. First answer my question, and then drink of the water and take away as much as thou mayst require.' Sahadeva, however, who was extremely thirsty, disregarding these words, drank of the water, and having drunk of it, dropped down dead.
Yudhisthira sent Arjuna also after it has been long time since his brothers went. He also saw his brothers dead and drank the water because he was thirsty.
Then Yudhishthira, the son of Kunti, said unto Vijaya, 'It is long since, O Vibhatsu, that thy two brothers have gone, O represser of foes! Blessed be thou! Do thou bring them back, together with water. Thou art, O child, the refuge of us all when plunged in distress!' Thus addressed, the intelligent Gudakesa, taking his bow and arrows and also his naked sword, set out tor that lake of waters. And reaching that spot, he whose car was drawn by white steeds beheld those tigers among men, his two younger brothers who had come to fetch water, lying dead there. And seeing them as if asleep, that lion among men, exceedingly aggrieved, raised his bow and began to look around that wood. But he found none in that mighty forest. And, being fatigued, he who was capable of drawing the bow by his left hand as well, rushed in the direction of the water. And as he was rushing (towards the water), he heard these words from the sky, 'Why dost thou approach this water? Thou shalt not be able to drink of it by force. If thou, O Kaunteya, can answer the question I will put to thee, then only shalt thou drink of the water and take away as much as thou requirest, O Bharata!' Thus forbidden, the son of Pritha said, 'Do thou forbid me by appearing before me! And when thou shalt be sorely pierced with my arrows, thou wilt not then again speak in this way!' Having said this, Partha covered all sides with arrows inspired by mantras. And he also displayed his skill in shooting at an invisible mark by sound alone. And, O bull of the Bharata race, sorely afflicted with thirst, he discharged barbed darts and javelins and iron arrows, and showered on the sky innumerable shafts incapable of being baffled. Thereupon, the invisible Yaksha said, 'What need of all this trouble, O son of Pritha? Do thou drink only after answering my questions! If thou drink, however, without answering my questions, thou shalt die immediately after.' Thus addressed, Pritha's son Dhananjaya capable of drawing the bow with his left hand as well, disregarding those words, drank of the water, and immediately after dropped down dead.
Yudhisthira sent Bhima also after the delay of Arjuna, Sahadeva, and Nakula. He saw his brothers, became thirsty despite the warnings and fell dead.
And (seeing Dhananjaya's delay) Kunti's son Yudhishthira addressed Bhimasena, saying, 'O represser of foes, it is a long while that Nakula and Sahadeva and Vibhatsu have gone to fetch water, and they have not come yet, O Bharata! Good betide thee! Do thou bring them back, together with water!' Thereupon saying, 'So be it,' Bhimasena set out for that place where those tigers among men, his brothers, lay dead. And beholding them, Bhima afflicted though he was with thirst, was exceedingly distressed. And that mighty armed hero thought all that to have been the act of some Yaksha or Rakshasa. And Pritha's son Vrikodara thought, 'I shall surely have to fight today. Let me, therefore, first appease my thirst.' Then that bull of the Bharata race rushed forward with the intention of drinking. Thereupon the Yaksha said, 'O child, do not commit this rash act! This lake hath already been in my possession. Do thou first answer my questions, and then drink and take away as much water as thou requirest!'" Vaisampayana continued, "Thus addressed by that Yaksha of immeasurable energy, Bhima, without answering his questions, drank of the water. And as soon as he drank, he fell down dead on the spot.
Then, Yudhisthira finally decides to go as to what happened and is in grief.
Then thinking that his brothers had left him long since, Yudhishthira waited for some time. And the king said unto himself again and again, 'Why is it that the two sons of Madri are delaying? And why doth the wielder also of the Gandiva delay? And why doth Bhima too, endued with great strength, delay? I shall go to search for them!' And resolved to do this, the mighty-armed Yudhishthira then rose up, his heart burning in grief. And that bull among men, the royal son of Kunti thought within himself. 'Is this forest under some malign influence? Or, is it infested by some wicked beasts? Or, have they all fallen, in consequence of having disregarded some mighty being?
He then saw his brothers dead and becomes sad.
Vaisampayana said, "Yudhishthira saw his brothers, each possessed of the glory of Indra himself, lying dead like the Regents of the world dropped from their spheres at the end of the Yuga. And beholding Arjuna lying dead, with his bow and arrows dropped on the ground, and also Bhimasena and the twins motionless and deprived of life, the king breathed a hot and long sigh, and was bathed in tears of grief.
The crane reveals itself and to drink water and revive his brothers, Yudhisthira has to answer the Yaksha's qquestions which he agrees and he successfully does.
Some of them are,
Do thou, O son of Kunti, first answer my questions, and then take away as much as thou likest!' Yudhishthira said, 'I do not, O Yaksha, covet, what is already in thy possession! O bull among male beings, virtuous persons never approve that one should applaud his own self (without boasting, I shall, therefore, answer thy questions, according to my intelligence). Do thou ask me!' The Yaksha then said, 'What is it that maketh the Sun rise? Who keeps him company? Who causeth him to set? And in whom is he established?' Yudhishthira answered, 'Brahma maketh the Sun rise: the gods keep him company: Dharma causeth him to set: and he is established in truth.'
Yaskha allows one brother of his to live and Yudhisthira asked for Nakula's life and Yaksha questioned Yudhisthira if he can choose Bhima or Arjuna.
The Yaksha said,--'Thou hast, O king truly answered who is a man, and what man possesseth every kind of wealth. Therefore, let one only amongst thy brothers, whom thou mayst wish, get up with life!' Yudhishthira answered,--'Let this one that is of darkish hue, whose eyes are red, who is tall like a large Sala tree, whose chest is broad and arms long, let this Nakula, O Yaksha, get up with life! The Yaksha rejoined,-'This Bhimasena is dear unto thee, and this Arjuna also is one upon whom all of you depend! Why, then, O king dost thou, wish a step-brother to get up with his life! How canst thou, forsaking Bhima whose strength is equal to that of ten thousand elephants, wish Nakula to live? People said that this Bhima was dear to thee. From what motive then dost thou wish a step-brother to revive? Forsaking Arjuna the might of whose arm is worshipped by all the sons of Pandu, why dost thou wish Nakula to revive?'
Yudhisthira explained that his father had two wives and he cannot forsake virtue so Nakula should live.
Yudhishthira said,--'If virtue is sacrificed, he that sacrificeth it, is himself lost. So virtue also cherisheth the cherisher. Therefore taking care that virtue by being sacrificed may not sacrifice us, I never forsake virtue. Abstention from injury is the highest virtue, and is, I ween, even higher than the highest object of attainment. I endeavour to practise that virtue. Therefore, let Nakula, O Yaksha, revive! Let men know that the king is always virtuous! I will never depart from my duty. Let Nakula, therefore, revive! My father had two wives, Kunti and Madri. Let both of them have children. This is what I wish. As Kunti is to me, so also is Madri. There is no difference between them in my eye. I desire to act equally towards my mothers. Therefore, let Nakula live?'
Yaksha is pleased and gives life to all his brothers.
The Yaksha said,--'Since abstention from injury is regarded by thee as higher than both profit and pleasure, therefore, let all thy brothers live, O bull of Bharata race!"
Thereafter,Yudhishthira wanted to know the true identity of the Yaksha and said:-
I ask thee that art incapable of being vanquished and that standest on one leg in the tank, what god art thou, for I cannot take thee for a Yaksha! Art thou the foremost of the Vasus, or of the Rudras, or of the chief of the Maruts? Or art thou the lord himself of the celestials, wielder of the thunder-bolt! Each of these my brothers is capable of fighting as hundred thousand warriors, and I see not the warrior that can slay them
At this the Yaksha replied:-
O child, I am even thy father, the Lord of justice, possessed of great prowess! Know, bull of the Bharata race, that I came hither desirous of beholding thee!. I am well-pleased to witness thy harmlessness; and, O sinless one, I will confer boons on thee. Do thou, O foremost of kings, ask of me boons. I shall surely confer them, O sinless one!
Yudhisthira then asked his first boon.
Therefore, the first boon that I shall ask, is, may that Brahmana's adorations to Agni be not interrupted!' The Yaksha said,--'O Kunti's son endued with splendour, it was I who for examining thee, was carrying away, in the guise of a deer, that Brahmana's fire-sticks! Thereupon that worshipful one said,--'I give thee this boon!
His 2nd boon was that Pandavas should be successful in their agyatavyasa:-
Yudhishthira said,--'We have spent these twelve years in the forest; and the thirteenth year is come. May no one recognise us, as we spend this year somewhere.
Yama told that he will give him his boon and told him to spend their agyatavyasa in Virata's kingdom which is the reason why they spent their 13th year in his kingdom.
'Vaisampayana continued,-'Thereat that worshipful one replied,--'I give this boon unto thee!' And then reassuring Kunti's son having truth for prowess, he also said, 'Even if, O Bharata, ye range this (entire) earth in your proper forms none in the three worlds shall recognise you. Ye perpetuators of the Kuru race, through my grace, ye will spend this thirteenth year, secretly and unrecognised, in Virata's kingdom! And every one of you will be able at will to assume any form he likes! Do ye now present the Brahmana with his fire-sticks. It was only to test you that I carried them away in the form of a deer!
Yama told how he was not satisfied and told Yudhisthira to ask for more boons and Yama told Yudhisthira how he and VIdura are actually his portions
O amiable Yudhishthira, do thou ask for another boon that thou mayst like! I will confer it on thee. O foremost of men, I have not yet been satisfied by granting boons to thee! Do thou my son, accept a third boon that is great and incomparable! Thou, O king, art born of me, and Vidura of portion or mine!"
3.The third boon:-
Thereat Yudhishthira said,--'It is enough that I have beheld thee with my senses, eternal God of gods as thou art! O father, whatever boon thou wilt confer on me I shall surely accept gladly! May I, O lord, always conquer covetousness and folly and anger, and may my mind be ever devoted to charity, truth, and ascetic austerities! The Lord of justice said,--'Even by nature, O Pandava, hast thou been endued with these qualities, for thou art the Lord of justice himself! Do thou again attain what thou asked for!"
Reference:-The Mahabharata Book 3: Vana Parva, Aranya Parva
After Yaksha Prashna, they think of spending their unrecognized year.
Vaisampayana said, "Listen, O lord of men, how thy great grandfathers passed the period of unrecognition in the city of Virata. Having in this way obtained boons from the god of Justice, that best of virtuous men, Yudhishthira, returned to the asylum and related unto the Brahmanas all that had happened. And having related everything unto them, Yudhishthira restored to that regenerate Brahmana, who had followed him the churning staff and the fire-sticks he had lost. And, O Bharata, the son of the god of Justice, the royal Yudhishthira of high soul then called together all his younger brothers and addressed them, saying, 'Exiled from our kingdom, we have passed twelve years. The thirteenth year, hard to spend, hath now come. Do thou therefore, O Arjuna, the son of Kunti, select some spot where we may pass our days undiscovered by our enemies.'"
Arjuna then lists some kingdoms which they may spend. They do consider to spend in Surasena kingdom and Surasena is the grandfather of Krishna.
Arjuna replied, "Even by virtue of Dharma's boon, we shall, O lord of men, range about undiscovered by men. Still, for purposes of residence, I shall mention some spots that are both delightful and secluded. Do thou select some one of them. Surrounding the kingdom of the Kurus, are, many countries beautiful and abounding in corn, such as Panchala, Chedi, Matsya, Surasena, Pattachchara, Dasarna, Navarashtra, Malla, Salva, Yugandhara, Saurashtra, Avanti, and the spacious Kuntirashtra. Which of these, O king, wouldst thou choose, and where, O foremost of monarchs, shall we spend this year?"
Yudhisthira then said that whatever Yama has said must come true and besides, he is attached to Pandavas, virtuous, powerful, and charitable.
Yudhishthira said "O them of mighty arms, it is even so. What that adorable Lord of all creatures hath said must become true. Surely, after consulting together, we must select some delightful, auspicious, and agreeable region for our abode, where we may live free from fear. The aged Virata, king of the Matsyas, is virtuous and powerful and charitable, and is liked by all. And he is also attached to the Pandavas. Even in the city of Virata, O child, we shall, O Bharata, spend this year, entering his service.