Yes, $y$ can violate the constraints. The one about box constraints ($0 \leq y \leq 1$) is OK by how $y$ is defined, the problem is the other one ($A^T y \leq b$). First I tried getting a feasibility proof unsuccessfully, then I decided to build a reproducible counterexample using Python: 

    import cvxpy as cp
    import numpy as np
    
    # Generate a random instance according to the conditions stated by OP (small c, larger n).
    n = 150
    c = 2
    
    # Build p, A and b, which are elementwise positive.
    np.random.seed(1)
    p = np.random.uniform(0, 1, n)
    A = np.random.uniform(0,1, (n,c))
    b = np.random.uniform(0,1, c)
    
    # Define and solve the CVXPY problem. 
    # Note that we'll solve the primal problem only to get the dual variable lambda^*
    x = cp.Variable(n)
    prob = cp.Problem(cp.Maximize(p.T@x),
                     [A.T @ x <= b, 
                      x <= 1,
                      x >= 0 ])
    prob.solve()
    
    print("A dual solution is")
    print(prob.constraints[0].dual_value)

    # Construct the suggested heuristic solution, starting from the dual solution:
    lambda_opt = prob.constraints[0].dual_value
    r = p - np.matmul(A, lambda_opt)
    y = (r > 0).astype(int)
    
    # Verify feasibility for y:
    print("Check nonpositive:", (A.T @ y) -b )

This piece of code outputs the array [0.138349, 0.11109537] at the last line, therefore, $A^T y - b \leq 0$ doesn't hold and $y$ is unfeasible. As a conclusion, without further information or hypotheses about $A, b$ and $p$, the proposed approach won't work in general.

Regarding the second part of your question, it reminds me about Approximation Algorithms. I cite from the [Wikipedia article][1]:
> In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one.

Assuming the problem of finding $\lambda^*$ easier as you mention, there are two scenarios: 

1) If you can find $\lambda^*$ by other means and not solving the linear problem nor its dual, then you could use complementary slackness conditions to try find $x^*$. This somewhat relates to what you are building with the binding/nonbinding dual constraints (i.e. $r_i$ values). There are several examples available on how to procede, like [here][2], [here][3] or [here][4].


2) If the dual problem is "easier" to solve, your approach sounds similar to using a primal-dual method. You can read an explanation on how it works at Section 5.1 of [this document][5], while [the original source where it was proposed for solving linear programs][6] is several decades old.<sup>1</sup>

The general idea will be as follows:

 1. Find a feasible dual solution $\lambda$.
 2. Given $\lambda$, find some $x$ that minimizes the violation of complementary slackness in the primal problem. (This is the step that reminds me of what you are trying to approach when constructing $y$).
 3. If complementary slackness holds, $y$ is optimal, and the algorithm terminates.
 4. Otherwise, change $\lambda$ so as to improve the dual objective, and go to 2. 

 

---
<sup>1</sup> Dantzig, George Bernard, Lester Randolph Ford Jr, and Delbert Ray Fulkerson. *A PRIMAL--DUAL ALGORITHM*. No. P-778. RAND CORP SANTA MONICA CA, 1956.


  [1]: https://en.wikipedia.org/wiki/Approximation_algorithm
  [2]: https://math.stackexchange.com/a/1781926/203744
  [3]: https://math.stackexchange.com/a/2711824/203744
  [4]: https://math.stackexchange.com/a/2005638/203744
  [5]: http://www.cse.chalmers.se/edu/year/2017/course/TDA206/lecture-notes-week-04.pdf
  [6]: https://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM1709.pdf