When wizard-born folks go from country to country by magical means such as Apparition, Portkey, Floo Powder, Broomstick, etc...., are they illegally entering that country in a "Muggle-sense?"
When I say "legal in a Muggle-sense", I mean like passports or IDs.
We see no evidence of such border enforcement in the books and the international travel which does take place does so freely and without hindrance.
That's not the say that national boundaries do not exist in the magical community. The Quidditch World Cup reveals that strong, distinct national identities are prevalent amongst witches and wizards. There are also separate Ministries of Magic for each country (for instance, the Bulgarian Ministry of Magic features in Goblet of Fire). The boundaries of countries in the magical world seem to match those of their Muggle equivalents.
Remember that the Triwizard Tournament and the Quidditch World Cup were both major international events which involved visitors travelling from abroad. These were Ministry-sanctioned trips and therefore legal; indeed, when it came to the Quidditch World Cup the Ministry actually organised transport for thousands of foreign visitors.
"So, been keeping busy, Barty?" said Bagman breezily.
"Fairly," said Mr Crouch dryly. "Organising Portkeys across five continents is no mean feat, Ludo."
(Goblet of Fire, Chapter 7, Bagman and Crouch).
However, there are also quite a few examples in the books of hassle-free international travel that was never approved by any Ministry.
Voldemort travelled to Nurmengard and back again. It's not clarified exactly where Nurmengard is but it seems to be somewhere in Eastern Europe. Voldemort used magical flight to pass across multiple international borders in order to get there.
...he could feel Voldemort flying through the sky from far away, over a dark and stormy sea, and soon he would be close enough to Apparate to them...
(Deathly Hallows, Chapter 23, Malfoy Manor).
Voldemort also travelled to Germany in his search for the Elder Wand. His trip from the UK to Germany isn't shown but obviously he would've had to get there somehow, quite possibly by utilising magical flight once again. We know he was in Germany because the woman he kills speaks German back to him.
"I want Gregorovitch."
"Er wohnt hier nicht mehr!" she cried, shaking her head. "He no live here! He no live here! I know him not!"
(Deathly Hallows, Chapter 12, Magic is Might).
These examples might be countered with the argument that nobody was going to stop Voldemort at a borderpoint, even if they were able to. He may or may not have been travelling on this evidence and, let's face it, he wouldn't have cared either way.
Hagrid, Madame Maxime and the Death Eaters went across multiple international borders on their trips to visit the Giants. This is the only canon reference that I could find to a border crossing.
"We chanced a bit o' magic after that, and it wasn' a bad journey. Ran inter a couple o' mad trolls on the Polish border, an' I had a sligh' disagreement with a vampire in a pub in Minsk, but apart from tha', couldn't'a bin smoother."
(Order of the Phoenix, Chapter 20, Hagrid's Tale).
The only problem Hagrid had with crossing the border was running into some trolls. It's possible, I suppose, that the trolls were acting as border guards but I think it's far more likely that Rowling was making a playful reference to Billy Goat Gruff. The trolls appear to be random bystanders on a journey that was entirely unimpeded by border enforcement by any of the various Ministries of Magic. Remember too that Hagrid was accompanied by a wild Mountain Giant on his return journey. He was hardly inconspicuous. It seems reasonable to conclude that Hagrid faced no official border-check because travel between different countries is free and unregulated in Harry Potter.
It's also worth mentioning that Bill Weasley worked abroad for a time in Egypt and that Charlie Weasley worked in Romania whilst Fleur Delacour (originally from France) came to live and work in the UK. People appear to be free to move between different countries at will. Immigration doesn't seem to be something the international wizarding community worries about, presumably because there are so few witches and wizards in comparison with the numbers of Muggles.
The most natural conclusion from Hagrid's story and the wider evidence is that there is no border enforcement in Harry Potter. International travel takes place freely and with no restrictions. This is the case regardless of whether the transportation method is magical or non-magical. Wizards and witches are therefore not breaking the law when they travel overseas.
