It seems to me that Decomposition works by erasing the fabric of reality that underpins an object. So, can it affect anything whose "material concept" either doesn't exist in the information dimension or if said concept is mapped onto a location that is explicitly "outside of reality" itself?
After having seen the anime and read some about the magic you mentioned, here's my take to your question:
It seems to me that Decomposition works by erasing the fabric of reality that underpins an object.
No, it does not. TheGamer007 is right in saying that Decomposition 'doesn't erase the concept or fabric, but rather splits it into the most basic components.' In the wiki, it is described as something that 'interferes with structural information.' Furthermore,: "...after identifying the design of any Eidos, Magic Sequence, or object, he can decompose the design. For physical objects, he can translate the physical object into signals, and then erase the base design at his leisure, breaking the inter-molecular bonds and so decomposing or disintegrating the target. For an information body (Magic Sequences), he can directly disassemble the design..."
Can it affect anything whose "material concept" either doesn't exist in the information dimension or if said concept is mapped onto a location that is explicitly "outside of reality" itself?
From my understanding, Tatsuya is able to use Decomposition because of his another ability called Elemental Sight, which is able to access the Information Dimension and obtain information about the Eidos of his target. 'Every person and object imprints their Eidos within the Information Dimension, and every system and type of magic projects Sequences onto the Eidos through it.' Your question assumes 1.) there is another dimension which can hold 'material concepts' other than the Information Dimension and 2.) that it is possible for an object's/person's Eidos to be mapped only in this dimension in the first place. Unless this theoretical 'second dimension' exists and that an object's/person's Eidos is only mapped here, then the scenario of an object or person existing without an Eidos in the Information Dimension is not possible in the first place. If, however, those two conditions are met, then, theoretically, Decomposition magic will not work on said object/person. However, if said object's/person's Eidos existed in the Information Dimension before it was moved to this second dimension, then in the case of Tatsuya, he can still harm them because of Elemental Sight. I'll explain it below.
If anyone that could, theoretically, attack Tatsuya from other dimensions/universes OR could hide their material data or locate it elsewhere apart from the information dimension, can they protect themselves from Decomposition?
First, as mentioned here, anything with a physical body will always have their Eidos imprinted in the Information Dimension. If that another dimension has its own Information Dimension then, yes, they cannot be harmed by Decomposition. However, if said another dimension shares the Information Dimension with the current dimension that Tatsuya is in, then, they can be harmed by Decomposition. Then, Could they hide their material data or locate it elsewhere apart from the information dimension to protect themselves from Decomposition? Yes, they can hide their material data and even place it in another dimension but Tatsuya can still harm them. Why? I answer this in the assumption that the person's/object's Eidos was formerly located in the Information Dimension. If this was the case, then Tatsuya will notice and can pinpoint where this 'lack of information' occurred. As mentioned here regarding Elemental Sight, '..only phenomena that obscure a target's information can offer some level of protection, but even then, such protection can be destroyed by some form of Decomposition, either singly or as part of a Loop Cast series. Completely hiding one's information does not prevent detection as Tatsuya will notice the lack of information..'. Therefore, it can be said that he can still locate said person/object and cast Decomposition magic on them since Elemental Sight works 'regardless of distance.'