At my LGS There is a player who has the nasty habit of having a messy battlefield. The other players have mixed opinions about whether or not is problematic. I have talked to him about this both during events and outside of events, but it hasn't been corrected. What is my responsibility here, as a judge? Obviously making it difficult for other players to tell whether his permanents are tapped or untapped is not something that we should allow, but the complaints are nonexistent from all but the more veteran competitors. Is anything other than reminders necessary? If so, what could even be done about this?

First off, as long as there are no complaints, I don't see that you “need” to do anything. And if it's only the “veteran competitors” that complain, have you considered that they may be overreacting (since more competitve players seem to see things more strict than the more casual crowd, in my experience)?

That said, if you think his layout is “too messy”, I see a few approaches.
1. Talk to him. Explain to him how players are expected to maintain a clear gamestate (I can't access the MTR right now, but there's a sentence or two in there about it, under the “responsibilities of different roles” for players, if I remember correctly). Explain to him why we expect that. Ask him why he lays out his battlefield like he does. You say you've talked to him, so maybe this avenue has been (mostly) exhausted, or maybe you could go a little more in-depth.
2. Be heavy-handed. Explain to him that he needs to be “less messy”, and what you mean by that. What should he do differently? Explain to him that he's been warned, and that further refusal to “clean up” his layout will draw Game Losses. He'll either clean up his layout, or stop attending your events. Since there seem to be not very many complaints, I'd say this is probably not the best approach.
3. Do step 1, and talk/explain to him again. Then explain that you do see his “messy layout” as a problem, and that you will almost certainly rule against him in situations where his messy battlefield played a role. That way you won't alienate that player as completely as you probably will with 2., but his messyness will cost him, and he will have an incentive to clean up.

Depending on why you think he is being messy, my choice of how to go about it might change. Is he being deliberately messy in order to confuse his opponents and create advantages for himself? Then, if he keeps it up after being told he needs to stop, he's probably somebody you don't want in your events anyway, and I probably wouldn't care about alienating him with a harsh approach. Or is he a new kid who's excited to be playing and who simply doesn't understand how and why his messy layout is a problem? Then maybe you just need a good bit of talking/explaining, and maybe one that is less instructing and more discussing (obviously I have no idea how your explaining so far has been).

The MTR does state that cards on the battlefield should be either at 180 degrees or 90 degrees so that could be used as a starting point to help with the tapped/untapped cards issue.

Since its an FNM I think your responsibility is to keep the games going so people can have fun and socialise which doesn't see, to be an issue from that I've read and if the veteran competitors find it too hard to understand what the board state is I think asking the veteran player what exactly is so difficult for him might be a good conversation starter.

Since it is Regular REL from what I understand of the JAR I don't think you should be heavy handed and the only things you can do is ask the player to be more careful or to DQ him for cheating.

Originally posted by Drake Blasdell:

I have talked to him about this both during events and outside of events, but it hasn't been corrected.

Maybe you can help correct this by showing him how to organize his cards on the table. Maybe he's not correcting it himself because he doesn't know how.

The next time you see him with a messy battlefield, ask him if it would be okay for you to interrupt the game and take a minute to help him arrange his cards so they are more organized on the table.

Like Sebastian mentioned, if it's just the veteran's complaining, I'd have to factor that into my view. Similarly, I'd need some more details about what “messy” means.

if their cards are not organized in any obvious way, but they're still clear and distinguishable, I don't there there's much that needs to be done. One extra thing I'd look out for here is the amount of time they spend on their turns. If their field is distinguishable but disarrayed, I'd expect to see longer turns than necessary. That's definitely something to address, and understanding how they are thinking about their field and helping them, to adjust for better mental shortcuts from there may be productive.

If he's doing a casual “tap 10-45 degrees” thing, I think that's worth talking about as well. If I can't easily tell the difference between a card being crooked and one that is tapped, that's a problem. I don't think it's reasonable to require your opponent to have to remember whether you intentionally tapped a permanent or whether it may have just been bumped while doing something else.

In the end, I suspect there are several problems going on here, and since it's not causing a mass distraction, I'd not focus too much on trying to fix all the problems at once. I really don't want to turn FNM into “I'm judging you as a person” night for them, which is how that sort of criticism can easily come off as.

At regular REL you can handle this organically by taking a look at the board state and asking questions… “Is that tapped or untapped?” “Is that card in your graveyard or on the battlefield?” “Is that enchantment on this creature or that?” “Why is there an instant on the battlefield?” “Why do you make your creatures climb over your lands to attack?”

YMMV with this approach but it should gently convey the message, “I'm confused about your boardstate, please clean it up.”

Obviously, be mindful of accidentally providing strategic advice, hence why I wouldn't advocate doing this at competitive.

Originally posted by Adam Zakreski:

YMMV with this approach but it should gently convey the message, “I'm confused about your boardstate, please clean it up.”

If they were the type of person to pick up on subtle hints, then their opponents complaining would have conveyed that message already. So either they didn't pick up on it or they don't care. I think it's better to be direct about it and say what you feel. (As in “I'm confused about your boardstate, please clean it up.”)

Originally posted by Jochem van 't Hull:

Adam Zakreski
YMMV with this approach but it should gently convey the message, “I'm confused about your boardstate, please clean it up.”

If they were the type of person to pick up on subtle hints, then their opponents complaining would have conveyed that message already. So either they didn't pick up on it or they don't care. I think it's better to be direct about it and say what you feel. (As in “I'm confused about your boardstate, please clean it up.”)

Or option three - the player does it on purpose to irritate their opponents. There's a lot more I want to say about this situation, but I don't want to overstep.

One idea is, if you do patrols around the room as a judge (or even after you're done your match, if he's still playing), walk by his game and see if you can understand the game state. If you can't, just calmly ask him, as a spectator (at Regular, spectators are allowed to interfere in the game to various extents, IIRC) and not as a judge, “is that permanent tapped or untapped?”, or some such question. Then he'll have to clean up his game state. After you've done this a couple times, if he hasn't straightened up, you might want to have a Talk (capital T for emphasis) with him about his messy play.

I probably wouldn't go farther than a Talk with this player unless he subsequently makes it obvious that he's doing this to gain strategic advantage, annoy his opponents, or whatnot. In that case, I'd say it's a Serious Problem and go from there.