Thanks for joining the challenge!
Questions (and my answers):
-Does the move deleter count as a facility? How about the move tutor? (If so, what counts as a "single use"? Can I have the move deleter delete a move from each of my pokemon if I only visit their house once, or can I only choose one move from one pokemon to delete?)
Nope, not a facility.
-For Department Stores, if you only visit one person at one counter and then leave the building, have you used up the whole building, or can you go back and talk to someone at a different counter?
One use per counter. I encountered a similar issue, but I decided that each counter should be a facility, just so that things don't get annoying.
-Similarly, can I bug the lava cookie lady 15 times and stock up on lava cookies before leaving forever, or can I only ever speak to her once?
You can only speak to her once. Again, this happened in my Sapphire run.
-Does it count as "using" a shop facility (mostly game corner or battle-point shop) if you look in to see what they have and leave without buying something? (It seems silly to save up game corner coins or battle points just to realize that you don't have enough for what you want when you finally get there!)
If you don't buy anything, it does not count as using the facility.
-Are you allowed to rebattle trainers, or does that fall under not making relationships with people?
Rebattling is fine.
-Does riding on Mr. Briny's boat (which you have to do at least twice anyway for story reasons) count as using a facility?
Mr. Briney does not count as a facility, just like HM02 (Fly) can be used many times.
I hope this answers your questions. If you have any more, just ask. Have fun!
Sorry, I did not phrase things well-enough. When I say catch, I mean to obtain it through any method. For instance, Kabuto counts as being caught on Cinnabar island. Sorry, that was my fault for a bad explanation.
I hope you enjoy the challenge!